Структурные свойства контекстно-свободных грамматик тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

московским государственный университет

им. М. В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519.765

ГОРБУНОВ КОНСТАНТИН ЮРЬЕВИЧ

СТРУКТУРНЫЕ СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК

01.01.06 — математическая логика, алгебра и теория чисел

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физико-математических наук, профессор Н. К. Верещагин

Москва — 1999

Оглавление

Введение 3

1. Основные определения. 12

§1.1. Определения ко второй главе ..............................12

§1.2. Определения к третьей главе................................15

2. Перечислимые семейства контекстно-свободных грамматик 20

§2.1. Свойства преобразователей ................................20

§2.2. Свойства КС-грамматик....................................27

3. Структурные свойства графовых КС-грамматик 33

§3.1. Понятие п-делимости графа и его свойства..............33

§3.2. Соотношение понятий п-делимости и древесной ширины

графа............................................................41

§3.3. Основная теорема о структурных свойствах..............47

§3.4. Случай планарных графов..................................57

§3.5. Применение к бесконечным графам........................60

Введение

Актуальность темы. Контекстно-свободные грамматики представляют собой исключительно важный тип грамматик, к которому пришли независимо друг от друга многие исследователи. Наиболее четкую и глубокую характеристику этого класса дал Н. Хомский [11], [12]. Важная роль КС-языков объясняется несколькими их особенностями:

• естественность методов порождения КС-языков с интуитивной точки зрения

• простота алгоритмов распознавания КС-языков

• возможность практического применения КС-языков при описании синтаксиса языков программирования и естественных языков

Идея КС-грамматик состоит в рассмотрении выводимого слова вместе с его выводом (точнее, деревом вывода), при этом вывод понимается как синтаксический анализ данного слова. Неединственность вывода на практике приводит к нарушению однозначности разбивки предложений языка на синтаксические единицы. Методы описания семантики языка и проверки корректности грамматики также предполагают ее синтаксическую однозначность. Поэтому, естественно потребовать единственность вывода, т.е. однозначность соответствующей КС-грамматики.

Класс однозначных КС-грамматик обладает лучшими алгоритмическими свойствами, чем класс всех КС-грамматик. Например, как показано в работе А. Л. Семенова [8], по произвольной однозначной КС-грамматике и произвольной регулярной КС-грамматике можно узнать, эквивалентны ли они (т.е. порождают ли они один и тот же язык). Как известно, для произвольных КС-грамматик проблема распознавания эквивалентности регулярной КС-грамматике не имеет решения.

С другой стороны, свойство КС-грамматики "быть однозначной" неразрешимо (см. например [4, стр. 307]). В связи с этим, в работе Ан. А. Мучника [7] поставлен следующий вопрос: можно ли перечислить какое-либо семейство однозначных КС-грамматик, порождающее все однозначные КС-языки? Если бы ответ был положительным, ситуацию можно было бы считать благоприятной.

Графовые контекстно-свободные грамматики, являясь обобщением словарных КС-грамматик, также имеют хорошие алгоритмические свойства. -Как заметил в работе [22] А. О. Слисенко, для семейства конечных графов,, выводимых в какой-то одной КС-грамматике, ряд известных проблем, КР-полны'х для произвольных графов, решается . за полиномиальное время (например, проблема существования в графе гамильтонова цикла). Вопрос о том, выводим ли граф в фиксированной грамматике, тоже решается полиномиальным алгоритмом. Существует сформулированная Ан. А. Мучником проблема, универсальная в некотором смысле для упомянутых классических проблем и им аналогичных. Эта проблема состоит в том, чтобы выяснить, верна ли для данного графа формула, бескванторная часть которой состоит из предиката, распознаваемого машиной Тьюринга специального вида, работающей на графах с размеченными вершинами и перенумерованными при каждой вершине ребрами и имеющей ограниченное число посещений каждой вершины. Кванторы всеобщности и существования берутся по разметкам — компонентам исходной разметки. Универсальность данной проблемы состоит в том, что в указанном виде представляются основные известные NP-пoлныe проблемы распознавания свойств графа. Для выводимого семейства графов, как показал Ан. А. Мучник (не опубликовано), эта проблема полиномиально решима. С другой стороны, для семейства графов, имеющих в качестве миноров неограниченно большие плоские квадратные решетки, она МР-полна (граф

А является минором графа если каждой вершине из А можно поставить в соответствие ненулевой связный подграф графа В (причем разным вершинам — непересекающиеся подграфы) и каждому ребру графа А поставить в соответствие ребро графа В, соединяющее те два подграфа, которые соответствуют концам ребра из А).

Поэтому, представляет интерес независимая от грамматик харак-теризация графов, для которых КР-проблемы указанного типа решаются за полиномиальное время. Кроме того, поскольку степень ветвления всех графов, выводимых в одной КС-грамматике, ограничена, представляет интерес обобщение понятия КС-выводимости на семейства графов с неограниченной степенью ветвления. Так, Н. Робертсон и П. Д. Сеймур предложили в [17] понятие древесной ширины графа и доказали в [16],[19], что для всех г существует т = /(г) такое, что любой граф, не имеющий в качестве минора плоской решетки размера г х г, имеет древесную ширину < т. Функция /(г) в их доказательстве имеет неэлементарный рост. В 1991 г. автор опубликовал оценку 7П = ехр(ро1у(г)) и метод, позволяющий доказать эту оценку. В 1994 г. Н. Робертсон, П. Д. Сеймур и Р. Томас опубликовали в [21] доказательство оценки т = 29г5. Их метод гораздо сложнее, чем метод автора, хотя он позволил достичь в показателе степени лучшей константы (5).

Цель работы. Основной целью работы является:

1. Получение ответа на вопрос о существовании перечислимого семейства однозначных КС-грамматик, порождающих все однозначные КС-языки.

2. Улучшение известных оценок размера графовых КС-грамматик, порождающих графы, не содержащие в качестве миноров решетки данного размера.

Методы исследования. В работе используется техника предста-

вления линейных КС-грамматик через преобразователи. Также используются комбинаторные методы, в частности, теоремы Рамсея и Менгера.

Научная новизна. Результаты диссертации являются новыми и состоят в следующем:

1) Доказано, что не существует перечислимого семейства КС-грамматик, порождающего класс однозначных языков. Попутно построен некоторый интересный класс грамматик, для которых проблема эквивалентности с произвольной КС-грамматикой имеет решение.

2) Получены верхние оценки древесной ширины графов, не содержащих в качестве миноров плоских решеток данного размера г х г. При этом, для произвольных графов соответствующая оценка имеет вид ехр(ро1у(г)), а для планарных графов получена линейная оценка. Из этих оценок следуют соответствующие оценки на минимальный размер графовой КС-грамматики, порождающей все графы, имеющие ограниченную степень ветвления и не содержащие в качестве миноров решеток данного размера.

Теоретическая и практическая ценность. Работа носит теоретический характер. Полученные результаты могут быть полезны специалистам в математической лингвистике и теории графов.

Аппробация. Результаты диссертации докладывались и обсуждались на Научно-исследовательском семинаре по математической логике механико-математического факультета МГУ под руководством С. И. Адяна и В. А. Успенского (в 1998 г.), а также на Колмогоровском семинаре кафедры математической логики и теории алгоритмов мех.-мат. факультета МГУ под руководством Н. К. Верещагина, А. Л. Семенова и А. X. Шеня (в 1996 г.) и на совместном семинаре МИР АН и ВЦ РАН по теории сложности под руководством А. А. Разборова и С. П. Тарасова (в 1998 г.).

Структура и объем работы. Диссертация состоит из введения и трех глав, разбитых на девять параграфов. Текст диссертации изложен на 67 страницах. Список литературы содержит 26 наименований.

Опишем кратко содержание работы.

Введение. Здесь описана постановка задач и их история, а также кратко сформулированы основные результаты диссертации.

В первой главе приводятся основные определения, используемые в работе. Здесь напоминаются определения контекстно-свободной грамматики и контекстно-свободного языка, их однозначности, детерминированного и недетерминированного преобразователя, графовой КС-грамматики, минора. Некоторые определения иллюстрируются примерами.

Во второй главе (параграф 2.2) определяется класс КС-грамматик, названных графиковыми. Это класс грамматик, порождающих языки, которые естественным образом представляют объединение графиков конечного числа детерминированных преобразователей с конечной задержкой. Доказывается основная теорема, которая утверждает, что:

а) существует алгоритм распознавания эквивалентности произвольной КС-грамматики и графиковой.

б) существует алгоритм, распознающий включение языка, порождаемого произвольной КС-грамматикой К, в язык, порождаемый графиковой грамматикой и, если это включение выполняется, то можно построить графиковую КС-грамматику, эквивалентную К.

в) множество графиковых КС-грамматик, порождающих однозначный язык, неперечислимо.

При доказательстве утверждений а), б) сформулированные проблемы для графиковых КС-грамматик сводятся к соответствующим проблемам для преобразователей. Существование решений для послед-

них доказывается в §2.1. А именно, описывается решение проблемы равенства графика Г недетерминированного преобразователя и объединения графиков детерминированных преобразователей и проблемы включения Г в это объединение.

При доказательстве утверждения в) каждой проблеме соответствия Поста ставится в соответствие графиковая КС-грамматика, которая задает неоднозначный язык тогда и только тогда, когда существует последовательность совпадения.

Из утверждений основной теоремы сразу следует ответ на вопрос, поставленный Ан. А. Мучником в [7]:

Теорема. Не существует такого перечислимого множества КС-грамматик (не обязательно однозначных), элементы которого порождают в точности все однозначные КС-языки.

В третьей главе изучаются структурные свойства графовых КС-грамматик. Известно [14], что все графы, выводимые в какой-либо одной КС-грамматике, во-первых, имеют ограниченную степень ветвления, а, во-вторых, не содержат в качестве миноров достаточно больших плоских квадратных решеток. В §3.3 доказывается обратное утверждение, т.е. что все графы, не содержащие решеток любого фиксированного размера, выводятся в некоторой КС-грамматике. Доказывается экспоненциальная от размера решетки верхняя оценка на минимальный размер этой грамматики. Данное утверждение является следствием более общего утверждения, являющегося результатом обобщения понятия КС-выводимости на семейства графов с неограниченной степенью ветвления.

Для проведения такого обобщения в §3.1 вводится понятие п-делимого графа. Рассматриваются процессы деления конечного графа на подграфы, состоящие в следующем: каждый неодновершинный подграф, возникший в процессе деления, на очередном шаге делится на

два подграфа, пока все подграфы не станут одновершинными. (Подграфом мы называем подмножество вершин графа вместе со всеми ребрами между ними. Таким образом, подграф однозначно определяется множеством своих вершин. Здесь и далее, когда мы говорим, что подграф делится на два подграфа (или на две части), мы имеем в виду, что на две части делится множество его вершин).

Определение. Конечный граф А называется п-делимым, если существует процесс его деления, в котором для каждого возникающего подграфа В можно так выделить не более п вершин в графе А, что любое ребро графа А, имеющее ровно один конец в В, инцидентно хотя бы одной из выделенных вершин.

Легко показать, что для произвольного семейства Б графов ограниченной степени ветвления следующие два утверждения эквивалентны:

1) Существует п такое, что все графы из Б п-делимы.

2) Существует КС-грамматика, в которой выводимы все графы из 5. Точнее, верно следующее утверждение.

Утверждение. Если все графы из Б п-делимы, то существует грамматика размера < 5(кп)4, в которой выводимы все графы из Б. Обратно, если все графы из Б выводимы в грамматике размера п, то они п-делимы (размером грамматики мы называем сумму числа вершин и ребер по всем правым частям ее правил).

Кроме этой эквивалентности, обобщающий характер понятия п-делимости подтверждается и тем, что вышеупомянутые положительные алгоритмические факты, касающиеся выводимости, сохраняются и для делимости (так, универсальная проблема и ее решение обобщены Ан. А. Мучником). В качестве примера, приводится обобщение на понятие делимости известного [22] алгоритма поиска вывода графа в данной КС-грамматике, основанного на методе динамического программирования. Конкретно, составляется список всех п-делимых

связных подграфов, начиная с меньших (подграф п-делим, если он п-делим как граф, но с учетом граничных ребер). Решение о занесении подграфа в список принимается, если хотя бы при одном способе разбиения его на части, эти части уже есть в списке.

В §3.2 выясняется связь понятия п-делимости с предложенным в [17] Н. Робертсоном и П. Д. Сеймуром понятием древесной ширины графа. Показывается, что древесная ширина графа линейно (в обоих направлениях) связана с минимальным п, для которого этот граф п-делим. Точнее, доказано, что

а) Граф древесной ширины п является (п + 1)-делимым.

б) п-делимый граф имеет древесную ширину не более 3п.

Таким образом, две эти характеристики графа можно считать эквивалентными.

В §3.3 доказывается основной результат:

Теорема. Для любого натурального г > 2 существует т < г2 ехр(г20) такое, что если конечный граф не имеет миноров, изоморфных плоской решетке размера г х г, то этот граф т-делим.

В силу результата из §3.2, аналогичная экспоненциальная оценка верна и для древесной ширины графа. Это улучшает очень большую верхнюю оценку на функцию /(г), следующую из доказательства Н. Робертсона и П. Д. Сеймура [16],[19] результата, упомянутого на стр. 5.

Как уже упоминаюсь, сформулированная теорема имеет также следствие:

Следствие. Для любых г, к существует т < 5кА ехр(г23) такое, что семейство конечных графов степени ветвления не более к, не имеющих миноров, изоморфных решетке размера г х г, выводимо в КС-грамматике размера т.

В §3.4 рассматривается случай планарных графов. Показывается,

что для них основная теорема из §3.3 верна с линейной оценкой:

Теорема. Для любого г существует т < сг, где с — 216, такое, что если конечный планарный граф не имеет миноров, изоморфных решетке размера г х г, то этот граф т-делим.

Это улучшает квадратичную оценку на функцию р(г), следующую из доказательства [18] Н. Робертсона и П. Д. Сеймура того факта, что для всех г существует т = р(г) такое, что любой планарный граф, не имеющий в качестве минора плоской решетки, размера г х г, имеет древесную ширину < т.

Так же, как и в общем случае, для планарных графов выполняется следствие:

Следствие. Для любых г, к существует т < скАгА (с = 267у) такое, что семейство конечных планарных графов степени ветвления не более к, не имеющих миноров, изоморфных решетке размера г х г, выводимо в КС-грамматике размера т.

В §3.5 описывается применение понятия делимости к счетным бесконечным графам. Доказывается утверждение типа "компактности", т.е. что из п-делимости каждого подграфа бесконечного графа С следует п'-делимость самого С, где п' = Зп + 3.

Автор пользуется случаем, чтобы выразить искреннюю благодарность Ан. А. Мучнику за постановку задач и плодотворные обсуждения, а также своему научному руководителю профессору Н. К. Верещагину за постоянное^внимание, помощь и поддержку при работе над диссертацией.

1. Основные определения. §1.1. Определения ко второй главе

Обозначим через А* множество всех слов в алфавите А, включая пустое слово, которое мы будем обозначать через Л. Языком назовем произвольное множество слов.

Определение. Контекстно-свободной грамматикой называется четверка Г = (Удг, УТ, Р, 5), где Удг и Ут — конечные алфавиты соответственно нетерминалов и терминалов, Р — конечное множество правил подстановки (продукций) вида А —у а, А Е Уы-> а £ (Уы и "Иг)*, а 5 — начальный символ из Удг.

Применение правила А —> а к слову V заключается в замене одного произвольного вхождения в v нетерминала А на слово а. Слово и) выводимо из слова V, если существует последовательность г>х,..., ип слов в алфавите Уи^Ут, в которой у\ = у, уп = ш и для каждого г < п слово Уг+1 получается из слова У{ применением одного из правил подстановки грамматики. Слово ш выводимо в грамматике, если оно выводимо из началь�