Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Заслуживает упоминания еще одно непосредственное следствие этих результатов о неразрешимости. Мы уже заметили (последний абзац разд. 1.5), что язык L регулярен тогда и только тогда, когда существует преобразователь Т, такой, что T(U)-L, где U есть множество всех цепочек в Vt . Как мы видели, из теоремы 25 следует, что не существует алгоритма, определяющего, является ли произвольный бесконтекстный язык регулярным, т. е. существует ли преобразователь Т, такой, что T(U) = L. Так как U есть бесконтекстный (даже регулярный) язык, то мы имеем следующую теорему.
Теорема 27. He существует алгоритма, определяющего по< заданным бесконтекстным языкам L1 и L2, существует ли конеч-
194
И. Хомский
ный преобразователь T, такой, что T(L1)-L2 (С. Гинзбург, личное -сообщение).
4.5. Структурная неоднозначность
Мы говорим, что бесконтекстная грамматика G неоднозначна, если она порождает цепочку х двумя существенно различными способами, т. е. если она ставит в соответствие цепочке х два различных структурных описания (см. стр. 170). Вопрос оструктурной неоднозначности важен с многих точек зрения, и хотя он до сих пор очень мало исследован, все же имеются некоторые результаты в этом отношении.
Рассмотрим сначала такой вопрос. Существует ли алгоритм, определяющий неоднозначность бесконтекстной грамматики? Отрицательный ответ прямо следует из неразрешимости проблемы соответствия. Действительно, предположим, ЧТО Е = |ЛС;,0(| 1-С*-Сл}, где JCi и у, — цепочки в некотором алфавите, скажем, в алфавите \а, Ь). Выберем п иовых символов dh...,dn и построим две грамматики Gx и Gv следующим образом:
Gx : Sx->- с, Sk -S- dtSxx’ (I c'і . 'n),
(42)
Gy: Sy-+с, Sy-+d,Syyi (1 ]i .п).
Ясно, что Gx и Gy однозначны, но заметим, что последовательность индексов (i!,...,Im), такая, что xit ...xlm—yu ...yi , существует тогда и только тогда, когда G1. и Gy обе порождают цепочку z, где
г = dt, . . . dj ex' . . . Xi = d, . . . d, си* . . . и;. (43)
'1 ‘т ‘т і і lm v,m v'\ к }
Таким образом, проблема соответствия для ? имеет положительное решение тогда и только тогда, когда существует цепочка г, которую порождают одновременно обе грамматики Gx и Gy, т. е. если неоднозначна грамматика Grv, которая содержит правила грамматики Gx, правила грамматики Gy и, кроме того, правила S-»SV, S->-S}1, где S является начальным символом грамматики Grv. Следовательно, не существует алгоритма, определяющего по произвольному множеству Е, будет лн грамматика Gxy, построенная указанным способом, неоднозначной.
T е о р е м а 28. He существует алгоритма, определяющего, является ли бесконтекстная грамматика неоднозначной (Шюценбер-же, личное сообщение).
Заметим, что грамматика Gxy принадлежит классу грамматик G, удовлетворяющих следующему условию:
Формальные свойства грамматик
195
G — линейная грамматика, обладающая по крайней мере тремя нетерминальными символами, все заключительные правила (44)
которой имеют вид а-*с, где с — символ, не встречающийся ни в одном нетерминальном правиле G.
Таким образом, мы видим, что проблема неоднозначности неразрешима уже для грамматик, удовлетворяющих этому условию.
Недавно было показано посредством обобщения проблемы соответствия, что условие (44) может быть ослаблено для случая одного нетерминального символа, и при этом неразрешимость проблемы неоднозначности остается в силе. Действительно, это обобщение позволяет отождествить S, Sx и Sy в грамматике Gjcy [23 І. Таким образом, теорема 28 имеет место для класса минимальных линейных грамматик G, удовлетворяющих условию:
G — линейная грамматика с единственным нетерминальным символом S и единственным терминальным правилом S->c, где с (45)
не встречается ни в одном из нетерминальных правил G.
Предположим, что G — минимальная линейная грамматика с нетерминальным правилом S-^xlSyi*, 1<'<п, связанным с множеством пар
E = )(*, у I) \ 1 -< і < п\.
G неоднозначна тогда и только тогда, когда существуют две последовательности индексов / и J
I — Он • • ¦ > i/), J — (А. ¦ ¦ • ,/j)>
i-4=j, і •: Lr i,„ »,
такие, что х^.^х^су .у,* =Xit...XjiiCyj*...yh*. Эго очередь верно тогда и только тогда, когда
(І) Xit . . . Xip ... Xh . . . Xk ,
(») Vi1 ¦ ¦ • Уі, Ун ¦ ¦ ¦ У},-
Ho рассмотрим вопрос:
Если задано множество E1 то существу кили последовательности индексов ] к J, заданные соотношениями (46), которые удовлетворяют условию (47)?
(46) в свою
(47)
(48)
196
Н. Хомский
Из теоремы 28, распространенной на минимальные линейные грамматики, следует, что этот вопрос, касающийся однозначной дешифровки, неразрешим.
В разд. 1.2 мы отметили, что для каждого конечного автомата мы можем построить эквивалентный ему детерминированный конечный автомат (и, конечно, вопрос об эквивалентности двух конечных автоматов разрешим). Другими словами, если задана односторонняя линейная грамматика G, то мы можем найти эквивалентную однозначную одностороннюю линейную грамматику. Очевидный вопрос состоит в том, верно ли это также для бесконтекстных грамматик в целом. Парих [49] показал, что это неверно.
