Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Свойства дополнения, вытекающие из предыдущих рассуждений
о пересечении, не переносятся непосредственно иа подтипы множества Y бесконтекстных языков; хотя из сказанного выше следует, что дополнение языка из X (или Im, или я) не обязательно принадлежит X (соответственно Xm ИЛИ о), HO нз этого не следует, что оно не принадлежит Однако вполне резонно предположить, что установ-ленный результат распространяется в на эти подсемейства. Очевидно,: вопрос о том, являетбя ли дополнение линейного языка с единственным нетерминальным символом (и с единственным заключительным правилом S-s.c, где с ие появляется нигде в остальных правилах) бесконтекстным языком — это очень важный вопрос остающийся пока открытым.
Как мы знаем, класс X1 регулярных языков замкнут относительно пересечения и дополнения (теорема 1, Г.^ЗД- 1-2)- Итак, в итоге мы имеем следующее: все типы бесконтекстных языков, установленные в определении 7 разд. 4.1, замкнуты относительно операции объединения, HO только X1 замкнут относительно пересечения и дополнения. Далее, пересечение языков типов X, Xm и а не обязательно вообще будет бесконтекстным (т.е. вообще будет в у).
Интересно отметить, что эти свойства не переносятся на контекстные языки. В частности, пересечение двух контекстных языков является контекстным языком 136]. Ho вопрос о дополнении контекстного языка остается открытым.
4.4. Неразрешимые свойства бесконтекстных грамматик
В разд. 3 мы показали, что многие проблемы, связанные с контекстными грамматиками, оказываются алгоритмически неразрешимыми. Некоторые, но не все, из этих проблем являются неразрешимыми также и в случае бесконтекстных грамматик — в действительности даже простейшего вида, выходящего за пределы конечных автоматов.
Прежде всего приведем теорему.
Теорема 22. Если задана бесконтекстная грамматика G, то существует алгоритм, определяющий, является ли язык, порождаемый грамматикой G1 пустым, конечным или бесконечным [41.
Отсюда следует, что систематическое изучение правил дает больше сведений о свойствах бесконтекстной грамматики, нежели контекстной грамматики. Однако во многих других отношениях мы сталкиваемся с сильными ограничениями, наложенными на то, что может быть определено этим способом. В обзоре, касающемся неразрешимости, мы будем в основном следовать Бар-Хиллелу, Перлсу и Шамиру [4 I.
т
Н. Хомский
. Известные неразрешимые свойства бесконтекстных грамматик следуют из сведения к проблеме !алгоритмическая неразрешимость которой была доказана Постом [501), называемой проблемой соответствия. Это может быть сформулировано следующим образом. Предположим, что нам задано множество E из п пар цепочек в алфавите из по меньшей мере двух букв. Тогда
2 = K-*!. Ух).....(*„. Уп)\-
Последовательность целых чисел
I = (h,-.., t'J, I
мы назовем последовательностью индексов для Е. Мы говорим, что последовательность индексов I удовлетворяет E только в том случае, если
Xlm У1т . (30)
Проблема соответствия состоит в том, что если задано множество E, то требуется определить, существует ли последовательность индексов /, удовлетворяющая множеству Е. Пост показал, что эта проблема алгоритмически неразрешима, т. е. не существует алгоритма, определяющего по заданной последовательности E пар цепочек, существует ли последовательность индексов, удовлетворяющая E. Заметим, что если / удовлетворяет Е, то II —(1Ъ...,ImtI1,... ..., In,) также удовлетворяет Е. Следовательно, либо не существует последовательности индексов, удовлетворяющей E, либо существует бесконечно много последовательностей индексов, удовлетворяющих Е, и в силу этого вопрос» существует ли бесконечное множество удовлетворяющих последовательностей, также алгоритмически неразрешим. Этот факт играет важную роль в последующих рассуждениях.
Ограничимся на некоторое время рассмотрением языков в алфавите \а, Ь,с\. Обозначим через L(G) язык, порождаемый грамматикой О; через L — дополнение к языку L (относительно алфавита >а, Ь, с); через L1OL1— пересечение L1 и L2; через L1U^a— объединение L1 и L3 и через х*— отражение цепочки х.
Допустим, что нам задано произвольное множество Е,
E = KJt1. л)...., (*., У»)), (31)
где для каждого і Xi и іпредставляют собой цепочки в алфавите (а, 6). Пусть G(E) — множество правил подстановки
S^c, S XtSy' (I -Ct-C п), (32)
Формальные свойства грамматик
189
порождающих язык L[G(E)]. Тогда G(E) есть линейная бесконтекстная грамматика с единственным нетерминальным элементом. Рассмотрим теперь вопрос, порождает ли G(E) цепочку zcz*. Ясно, что это верно лишь в том случае, когда существует последовательность ийдексов Oi,...,для множества Е, такая, что
Z = Xll...xtm = yh.(33)
Таким образом, проблема определения, порождает ли произвольная линейная грамматика G (с одним нетерминальным символом) цепочку вида zcz* для некоторого Z, есть в точности проблема соответствия Поста (см. работу [63]). Следовательно, не существует общего метода определения, порождает ли заданная бесконтекстная грамматика G (которая может быть даже линейной с одним нетерминальным символом) некоторую цепочку zcz*, а следовательно, и бесконечное множество таких цепочек (как это было выше замечено), или же она не порождает ни одной такой цепочки.
