Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Сокращение выводов. Пусть в некоторой грамматике имеется вывод А ф, где А — нетерминальный символ, а ф — произвольная цепочка. Очевидно, мы не изменим язык, порождаемый этой грамматикой, если добавим к ней правило А—»ф. Будем говорить, что это правило получено сокращением вывода.
7.2.3. Непустые, конечные и бесконечные языки
Непустые языки. Необходимым и достаточным условием непустоты языка, порождаемого КС-грамматикой G, является существование вывода S=^t, где т — терминальная цепо^к^. 120
Часть II. Некоторые замечательные классы языков
Проблема существования такого вывода разрешима (см. посвященное этому упражнение).
Бесконечные языки. Поскольку терминальный словарь конечен, необходимым условием бесконечности языка L(G) является неограниченность длин выводимых терминальных цепочек. Отсюда следует, что длины выводимых предтерминальных цепочек также не должны быть ограничены; стало быть, не должны быть ограничены и длины выводимых нетерминальных цепочек.
Это последнее условие явно не является достаточным, поскольку возможны грамматики, в которых длины нетерминальных цепочек не ограничены, но которые тем не менее порождают пустой язык').
Тем самым мы можем расчленить проблему бесконечности языка на две, а именно:
а) Найти необходимое и достаточное условие бесконечности множества порождаемых грамматикой нетерминальных цепочек.
б) Найти дополнительное условие бесконечности множества терминальных цепочек.
Чтобы ответить на вопрос а), рассмотрим граф, определенный на стр. 119; при этом будем считать грамматику связной.
Этот граф может содержать цикл или петлю, начинающуюся, скажем, в Л и возвращающуюся в Л. В этом случае существует вывод вида
Л фЛф.
Тривиальный случай Л =^ Л соответствует простому повторению Л. Исключим из рассмотрения этот случай, положив
I Ф I-H ф M=O.
Поскольку рассматриваемая грамматика является по предположению связной, в ней существует вывод вида
Следовательно, множество порождаемых грамматикой нетерминальных цепочек («нетерминальный язык») содержит бесконечное множество цепочек вида оирМф1^ и тем самым является бесконечным,
Предположим теперь, что наш граф не содержит ни петель, ни циклов. Тогда правила вида Л і—не могут содержать в правых частях Ai. Если правая часть такого правила содержит A2, то правила вида A2-*фг не могут содержать в правых частях ни Ait ни A2 и т. д. Таким образом, нетерминальные символы постепенно исчезают, и после конечного числа шагов их не будет вовсе, так
') Такова, в частности, грамматика G0 на стр. 117,—Прим. ред, Гл. VlL Контекстно-свободные яшки
121
что порождаемый грамматикой «нетерминальный язык» не может быть бесконечным.
Итак, для того чтобы порождаемый грамматикой нетерминальный язык был бесконечным, необходимо и достаточно, чтобы для некоторого нетерминального символа А существовал вывод
ЛфсрЛф, |ср| + Ц>М=0.
Нетрудно доказать, что проблема существования такого нетерминального символа алгоритмически разрешима.
Если |ф| • |г|з| ?=0, говорят, что символ А самовставляющийся.
Что касается вопроса б), то для него также можно указать разрешимый критерий (см. упр. 7 на стр. 123). Таким образом, проблема распознавания конечности языка является разрешимой. Разрешима и проблема распознавания пустоты (см. упр. 6 на стр. 123). Итак, имеет место
Теорема. Свойства КС-грамматики порождать пустой язык и порождать конечный язык (а следовательно, и свойства порождать непустой или бесконечный язык) алгоритмически распознаваемы.
7.2.4. Рекурсивность
Поскольку КС-грамМатики имеют довольно специальную форму, можно ожидать, что и порождаемые ими языки являются языками какого-то специального вида.
Так как мы исключили правила вида А—*Е, на каждом шаге вывода в КС-грамматике длина цепочки может только увеличиваться или в крайнем случае оставаться неизменной. Чтобы ответить на вопрос, принадлежит ли данная цепочка (не обязательно терминальная) языку, порождаемому данной КС-грамматикой, достаточно построить все возможные в этой грамматике выводы, начинающиеся начальным символом и оканчивающиеся цепочками, длины которых меньше или равны длине рассматриваемой цепочки. Указанная процедура применима для любой цепочки и всегда дает ответ «да» или «нет». Короче говоря,
всякий КС-язык является рекурсивным множеством.
7.2.5. Пример языка, не являющегося КС-языком
В дальнейшем нам понадобится тот факт, что язык L = = {апЬпсп} не является КС-языком. Докажем это утверждение.
Допустим, что L порождается некоторой КС-грамматикой. Поскольку L бесконечен, в этой грамматике существует вывод
А =#> «рЛф, I ф 1 +1 ф I ф 0. Поэтому в ней выводимы нетерминальные цепочки вида
cupMV? 122
Часть II. Некоторые замечательные классы языков
для любого п. В конце концов ф, А и должны дать терминальные цепочки. Сокращая соответствующие выводы, мы можем прибавить к нашей грамматике правила вида А-+ т.
Легко показать, что, какие бы правила такого вида мы ни выбирали, мы будем получать, помимо цепочек апЬпсп, также и другие цепочки, в которых показатели степени при а, Ь, с не будут равны.
