Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Ho пусть теперь Gm есть грамматика
S->¦ с, S-^aSa, S-^bSb, (34)
порождающая «зеркальный» язык L(Gm) — [zcz*}. Пусть G(E) задано равенством (32). Рассмотрим вопрос:
какова мощность множества L (Gm) П L [G (E)] ? (35)
Ho это есть в точности вопрос: сколько цепочек вида zcz* порождает грамматика G(E)? Мы знаем, что ответ на этот вопрос таков: либо ни одной, либо бесконечное множество, и мы только что обнаружили, что не существует алгоритма, определяющего, который из двух случаев имеет место. Следовательно, не существует алгоритма, определяющего для заданного множества E1 является ли L(Gn) п L [G(E) J Пустым илн бесконечным.
Отметим далее, что никакое бесконечное подмножество языка L(Gm) не является регулярным языком. Поэтому пересечение L(Gm) L[G(E) ] регулярно только в том случае, если оно конечно, т. е. пусто. Так как не существует алгоритма, обнаруживающего этот факт, то не существует алгоритма, определяющего для произвольного Е, является ли L(Gm) (\ LlG(Z)) регулярным языком.
T е о р е м а 23. He существует алгоритма, определяющего для заданных бесконтекстных грамматик G1 и G2, является ли язык L(G1)O^(G2) пустым, бесконечным или регулярным [4].
В действительности, это верно даже в том случае, когда G1 фиксирована и задана соотношением (34), a G2— линейна с единствен-
190
Я. Хомский
ным нетерминальным символом (так же, как и G1). Линейные грамматики с одним нетерминальным символом представляют собой в рамках наших исследований простейшие системы выше уровня конечных автоматов; а хорошо известно, что существует алгоритм, определяющий, является ли пересечение двух регулярных языков пустым или бесконечным (оно всегда регулярно).
Мы описали грамматику Gm в соотношении (34) как грамматику, порождающую «зеркальный» язык с заданной средней точкой. Пусть Gm2— грамматика, состоящая из правил (34) и правила
S1 -s. ScS. (36)
Пусть S1— начальный символ в Gm3. Тогда L(Gm3) состоит из всех цепочек вида хсх*сусу*, где.* и у— цепочки в алфавите (а, 6).
Пусть опять S задано соотношением (31); определим Gm(E) как грамматику, содержащую правила (32) грамматики G(E) и, кроме того, правила
S1-+ a .S1O, S1 -?- bS1 Ь, S1 ->¦ cSc, (37)
где S1— начальный символ. Грамматика Gm(E) вкладывает язык LlG(E)], заданный правилами (32), в «зеркальный» язык. Это значит, что LlGm(E) ] состоит в точности из тех цепочек вида xcyczcx*, в которых усг порождается грамматикой G(E); Gm (E) является своего рода «слиянием» грамматик Gm и G(E).
Рассмотрим теперь пересечение языков, порождаемых грамматиками Gm8 и Gra(E) (так же как раньше мы рассматривали пересечение L(Gm) и L[G(E)]]. Это есть множество L(Gm3)f|L [Gm(E)], состоящее в точности из тех цепочек х, которые удовлетворяют следующим условиям:
(i) X = XlCX1CX3CXi (X1 — цепочка в алфавите (а, 61),
(ii) Xl=^xl и Xi-Xl' (так как х(ZL(Gm))
(iii) X1 = х\ и Je2CJt3^L [G(E)] (так как х ? L [Gm (E)]). (38)
Тогда, в частности, JC1=JC3, Jt2=JC4 и X2=JC3' . Следовательно, L(Gmi) П LIGm(E) ] пусто, лишь когда не существует последовательности индексов, удовлетворяющей Е, и бесконечно в противном случае, в точности так же, как и раньше (потому что, как мы уже заметили, вопрос о том, существует ли цепочка х2сх3? L [G(E) ], где Jp2=Jc3* , есть в точности проблема соответствия для Е). Следовательно, не может существовать алгоритм, определяющий, является лн L(Gm2) П L[Gm(E) 1 пустым или бесконечным (имеются только эти две возможности).
Формальные свойства грамматик
191
Каждая цепочка в L(Gm2) П L [Om(S) ] имеет вид хсх* схсх", и легко показать, что никакое бесконечное множество таких цепочек не образует бесконтекстного языка. Следовательно, множество
L (Gm) П L \Gm (E)J
представляет собой бесконтекстную грамматику лишь в случае, когда оно конечно, т. е. пусто, и так как вопрос о непустоте, как было отмечено, неразрешим, то и вопрос, является ли
L (G2m) Г\ L [Gm (Е)| бесконтекстным языком, также неразрешим.
Теорема 24. He существует алгоритма, определяющего по заданным бесконтекстным грамматикам G1 и Gi, является ли L(G1) П L(Gj) бесконтекстным языком [41.
В действительности, это верно даже в том случае, когда G1 фиксирована в виде Gm2 и G2— мета-линейна (заметим, что Gma также мета-линейна). Теорема 23, впрочем, следует из рассуждений, доказывающих теорему 24.
Мы рассмотрели языки в алфавите (о, Ь, с), но при соответствующем кодировании мы легко можем распространить эти результаты о неразрешимости на языки в алфавитах из двух или более символов (см. работу 141).
В работе [4] доказательство теорем 23 и 24 состоит в основном в следующем. Рассмотрим множество E1 заданное соотношением (31). Пусть Lb— язык, состоящий из всех цепочек
аЬ'к . . .ab' CXil • • ¦ xIk сУі, ¦¦¦ У it c^h а ... b‘'a, (39)
где (('i,..-,(A) и (J1,¦..,/() — последовательности индексов для E-Легко показать, что Ls является бесконтекстным языком, порождаемым грамматикой Gs . Так определенная грамматика Gi будет играть ту роль, которую играла грамматика G71(E) в кратко описанном выше доказательстве.
