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

• Автор: Горбунов, Константин Юрьевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 67 с.

Оглавление
Введение
1. Основные определения
§1.1. Определения ко второй главе
§1.2. Определения к третьей главе
2. Перечислимые семейства контекстно-свободных грамматик
§2.1. Свойства преобразователей
§2.2. Свойства КС-грамматик
3. Структурные свойства графовых КС-грамматик
§3.1. Понятие гг-делимости графа и его свойства
§3.2. Соотношение понятий п-делимости и древесной ширины
графа
§3.3. Основная теорема о структурных свойствах
§3.4. Случай планарных графов
§3.5. Применение к бесконечным графам

Введение
Актуальность темы. Контекстно-свободные грамматики представляют собой исключительно важный тип грамматик, к которому пришли независимо друг от друга многие исследователи. Наиболее четкую и глубокую характеристику этого класса дал Н. Хомский [11], [12]. Важная роль КС-языков объясняется несколькими их особенностями:
• естественность методов порождения КС-языков с интуитивной точки зрения
• простота алгоритмов распознавания КС-языков
• возможность практического применения КС-языков при описании синтаксиса языков программирования и естественных языков
Идея КС-грамматик состоит в рассмотрении выводимого слова вместе с его выводом (точнее, деревом вывода), при этом вывод понимается как синтаксический анализ данного слова. Неединственность вывода на практике приводит к нарушению однозначности разбивки предложений языка на синтаксические единицы. Методы описания семантики языка и проверки корректности грамматики также предполагают ее синтаксическую однозначность. Поэтому, естественно потребовать единственность вывода, т.е. однозначность соответствующей КС-грамматики.
Класс однозначных КС-грамматик обладает лучшими алгоритмическими свойствами, чем класс всех КС-грамматик. Например, как показано в работе А. Л. Семенова [8], по произвольной однозначной КС-грамматике и произвольной регулярной КС-грамматике можно узнать, эквивалентны ли они (т.е. порождают ли они один и тот же язык). Как известно, для произвольных КС-грамматик проблема распознавания эквивалентности регулярной КС-грамматике не имеет решения.
С другой стороны, свойство КС-грамматики “быть однозначной” неразрешимо (см. например [4, стр. 307]). В связи с этим, в работе Ан. А. Мучника [7] поставлен следующий вопрос: можно ли перечислить какое-либо семейство однозначных КС-грамматик, порождающее все однозначные КС-языки? Если бы ответ был положительным, ситуацию можно было бы считать благоприятной.
Графовые контекстно-свободные грамматики, являясь обобщением словарных КС-грамматик, также имеют хорошие алгоритмические свойства. -Как заметил в работе [22] А. О. Слисенко, для семейства конечных графов,, выводимых в какой-то одной КС-грамматике, ряд известных проблем, КР-полных для произвольных графов, решается за полиномиальное время (например, проблема существования в графе гамильтонова цикла). Вопрос о том, выводим ли граф в фиксированной грамматике, тоже решается полиномиальным алгоритмом. Существует сформулированная Ан. А. Мучником проблема, универсальная в некотором смысле для упомянутых классических проблем и им аналогичных. Эта проблема состоит в том, чтобы выяснить, верна ли для данного графа формула, бескванторная часть которой состоит из предиката, распознаваемого машиной Тьюринга специального вида, работающей на графах с размеченными вершинами и перенумерованными при каждой вершине ребрами и имеющей ограниченное число посещений каждой вершины. Кванторы всеобщности и существования берутся по разметкам — компонентам исходной разметки. Универсальность данной проблемы состоит в том, что в указанном виде представляются основные известные КР-полные проблемы распознавания свойств графа. Для выводимого семейства графов, как показал Ан. А. Мучник (не опубликовано), эта проблема полиномиально решима. С другой стороны, для семейства графов, имеющих в качестве миноров неограниченно большие плоские квадратные решетки, она МР-полна (граф

вышает (кп)г. Правила Г имеют вид:
где х — (начальный) нетерминал, і — терминал, степени всех вершин < кп. Очевидно, размер Г не превышает 5(кп)4.
Пусть теперь выполнено условие 2, а размер грамматики равен п. Сначала докажем лемму, показывающую, что можно рассматривать только такие грамматики, в которых все незаключительные правила увеличивают число вершин графа.
Лемма 7. Для любой графовой КС-грамматики Г существует, эквивалентная ей графовая КС-грамматика Ті, в которой нет правил вида £ —у Е, где Е — одновершинный граф с вершиной, помеченной нетерминалом.. В правых частях правил Г стоят те же графы (кроме разметки), которые уже были в Г.
Доказательство. Рассмотрим ориентированный граф О, вершинами которого являются нетерминалы грамматики Г, а любые два нетерминала и £2 соединены направленным ребром тогда и только тогда, когда в Г существует правило ф —> гДе £2 — одновершин-
ный граф с вершиной, помеченной £2- Граф О разбивается на частично упорядоченное множество классов взаимно достижимых вершин. Для каждого класса все его элементы заменим одним нетерминалом. Оставшиеся “междуклассовые” правила вида £1 —У £2 ликвидируем, добавив для каждого правила £2 —У С правило —У Є. Очевидно, что полученная грамматика эквивалентна Г. Лемма 7 доказана.
Теперь процессу вывода легко сопоставляется процесс деления выведенного графа. При этом, каждому применению правила вывода £ —У С соответствует разделение подграфа, выведенного из нетер-