Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Рассмотрим теперь язык Lm, состоящий из цепочек
X1CX2CXt2 сх], (40)
где X1 и —цепочки в алфавите (а, 6|. Язык Lw также представляет собой бесконтекстный язык, порождаемый грамматикой Gm', эта грамматика будет играть роль грамматики Gm2 в доказательстве, приведенном выше.
Заметим теперь, что Lm П Ls является множеством всех цепочек
abik... Ob^1CXk ...XiCyik ...у-^cbail ...b^a, (41)
где Xil ...Xik=Uil-Vijt, т- е- где I1..('* есть последовательность
индексов, удовлетворяющая множеству Е. Следовательно, в силу
192
Н. Хомский
рассуждений, приведенных выше, если существует последовательность индексов, удовлетворяющая Е, то LmQLe бесконечно и не является ни регулярным языком, ни бесконтекстным языком; если не существует последовательности индексов, удовлетворяющей Е, то Lm П La пусто (и, следовательно, тривиально, является регулярным языком и бесконтекстным языком). Отсюда следует, что неразрешимость проблемы соответствия Поста влечет неразрешимость проблемы определения, является ли Lm П Li для произвольного множества S пустым, конечным, регулярным языком или же бесконтекстным языком (теоремы 23 и 24).
С помощью конструкции, слишком сложной, чтобы приводить ее здесь, в работе [4 ] показано, что для каждого E дополнение L і языка La представляет собой бесконтекстный язык. Легко показать, что дополнение Lm языка Lm есть бесконтекстный язык. Объединение двух бесконтекстных языков есть бесконтекстный язык. Следовательно, для каждого множества E язык Lm U Lm-Lm f) Ls представляет собой бесконтекстный язык. Дополнение этого языка равно Lm П Ls, а мы уже отметили, что не существует алгоритма, определяющего, является ли это множество пустым, конечным, регулярным или бесконтекстным. Каждый шаг конструктивен. Следовательно, мы имеем результат в форме теоремы.
Теорема 25. He существует алгоритма, определяющего по заданной бесконтекстной грамматике G, является ли язык L(G) (дополнение языка, порождаемого грамматикой G, относительно алфавита {а, Ь, с\) пустым, конечным, регулярным или бесконтекстным [4].
В частности, не существует алгоритма, определяющего, порождает ли произвольная бесконтекстная грамматика все цепочки в своем терминальном словаре, т. е. является ли она универсальной, и не существует алгоритма, определяющего, порождает ли произвольная бесконтекстная грамматика регулярный язык (так как это верно лишь в том случае, когда дополнение языка, порождаемого этой грамматикой, является регулярным языком).
В конце разд. 4.3 мы заметили, что неизвестно, является ли дополнение языка, порождаемого линейной грамматикой с одним нетерминальным элементом (простейший тип нерегулярного языка), бесконтекстным языком. Если ответ на этот вопрос положителен, то дополнение языка LlG(E)], порожденного грамматикой G(E), заданной соотношением (32), является бесконтекстным языком. Легко показать, что дополнение языка L(Gn), порождаемого Gn из (34), есть бесконтекстный язык. Следовательно, приведенным рассуждением мы можем показать, что ие существует алгоритма, определяющего, является ли дополнение
Формальные свойства грамматик
193
бесконтекстного языка (именно объединение дополнений этих линейных языков) пустым, конечным или регулярным. Более того, дополнение языка LIGm2] (см. правило 36) есть бесконтекстный язык и дополнение языка LtGm(E)] есть бесконтекстный язык, если дополнение языка LIG(E)] есть бесконтекстный язык. Отсюда следует, что мы могли бы полностью доказать теорему 25, не принимая во внимание язык L2 , заданный соотношением (39), а также конструкцию, которая дает его дополнение, при условии, что дополнение языка, порождаемого линейной грамматикой с одним нетерминальным элементом, есть бесконтекстный язык. Однако этот вопрос, очевидно, не прост.
Построение дополнения языка Le , данное Бар-Хиллелом, Перл-сом и Шамиром, приводит к доказательству факта, что для определенного типа линейных грамматик с одним нетерминальным элементом дополнение является линейным. В работе 169] доказано, что для более общего класса линейных грамматик с определенными центральными символами и одним нетерминальным (именно тем, для которого цепочка, расположенная вправо от центрального символа в порождаемой грамматике, однозначно определяется по цепочке, стоящей слева) дополнение является линейным. Ho общий вопрос остается открытым даже для линейных грамматик с единственным нетерминальным символом и указанным центральным символом. Из теоремы 25 немедленно следует теорема.
Теорема 26. He существует алгоритма, определяющего по заданным бесконтекстным грамматикам G1 и G2, имеет ли место равенство L(G1)=L(G2) [4].
Если бы такой алгоритм существовал, то можно было бы в общем случае определить, является ли L(G1) универсальным языком в противоречие с теоремой 25. Немедленно также следует, что проблема определения, имеет ли место включение L(G1)CiL(G2), алгоритмически неразрешима (это, впрочем, следует также из теоремы 23, так как L(Gra) есть бесконтекстный язык и HG(Z)] включается в него лишь в том случае, когда его пересечение с L(G01) пусто).
