имеет два дерева вывода, показанные на рис. 2.18. Дерево а предполагает интерпретацию

if & then (if b then a) else a

тогда как дерево б дает

if b then (if Ь then а else tz) □

Нам хотелось бы иметь алгоритм, который по произвольной КС-грамматике выясняет, однозначна ли она, но, к сожалению, такого алгоритма не существует.

Н" * then

If & then

it д then S else

Рис. 2.18- Два дерева вывода.

Теорема 2.30, Проблема, однозначна ли КС-грамматика G, неразрешима.

Доказательство. Пусть C = (Xi, i/i), (x,ji/J-частный случай проблемы соответствий над алфавитом 2. Возьмем КС-грамматику G-({5, Л, В}. 2 и/. Л 5), где / = {1, 2, ..., п} и Р содержит правила

А -» XiAi I Xii для 1 < t < /г В -> yiBi I yii для К i < АХ

Нетерминалы Aw В порождают соответственно языки Lq и Мс, определенные в разд. 2.6.3. Легко видеть, что не существует цепочки с двумя различными левыми выводами из нетерминала Л

или ИЗ нетерминала В. Следовательно, если существует цепочка с двумя различными левыми выводами из 5, то один должен начинаться шагом 5= Л, а другой - шагом S=iB. Но по.лемме 2.29 некоторая цепочка выводится из Л н из S тогда и только тогда, когда частный случаи С проблемы соответствий Поста имеет решение.

Таким образом, КС-грамматика G неоднозначна тогда и только тогда, когда С имеет решение. Отсюда сразу заключаем, что если бы существовал алгоритм, решающий проблему однозначности для КС-грамматик, то была бы разрешима проблема соответствий. □

Определенная нами неоднозначность - это свойство грамматики, а не языка. Для некоторых неоднозначных грамматик можно построить эквивалентные им однозначные грамматики.

Пример 2.46. Рассмотрим грамматику и язык из предыдущего примера. Грамматика G иеодпозначна потому, что else можно ассоциировать с двумя разными then. По этой причине языки программирования, в которых разрешаются как операторы вида, if-then, так и операторы вида if-then-else, могут быть неоднозначными. Неоднозначность можно устранить, если догово-риться> что else должно ассоциироваться с последним из предшествующих ему then, как на рис. 2.18,6.

Можно подправить грамматику из примера 2.45, введя два нетерминала 5 и 5,, и потребовав, чтобы порождал операторы вида if-then-else, тогда как 5 может порождать операторы обоих видов. Правила новой грамматики таковы:

5i if 6 then 5i (ff 6 then else 5 a S-Wb then 5, else 5„ I a

Tot факт, что слову else предшествует только S, гарантирует появление внутри конструкции then-else либо символа а, либо другого else. Таким образом, структура, изображенная на рис. 2.18, а, не возникнет. В гл. 5 мы изложим детерминированные методы разбора для различных грамматик, в том числе для грамматики этого примера, и там мы сможем доказать, что наша новая грамматика однозначна. П

Хотя нет общего алгоритма, выясняющего, однозначна ли грамматика, можно указать некоторые встречающиеся в правилах, конструкции, приводящие к неоднозначности. Поскольку неоднозначные грамматики часто анализируются труднее, чем однозначные, мы назовем здесь несколько наиболее распространенных конструкций такого "рода, так что их можно будет распознать на практике.

Приведенная грамматика, содер}кащая правила Л->ЛЛа, неоднозначна, так как подцепочка АЛА допускает два разных разбора (рис. 2.19).

Эта неоднозначность исчезнет, если вместо правил А-*АА\а взять правила

А-АВ\В

или правила

А-ВА\В В-а

Другой пример неоднозначности -правило Л-+ЛаЛ. Пара правил А-t-alp тоже создает неоднозначность, так как це-

/\ А А

А А

Рис. 2.19. Да дерева разбора.

почка аЛр имеет два разных левых вывода Л=аЛ=фаЛр и Л=фЛр=аЛр. В качестве более тонкого примера пары правил, из-за которых грамматика может стать неоднозначной, приведем Л-*-аЛаЛрЛ. Другие примеры неоднозначных грамматик можно найти в упражнениях.

КС-язык называется неоднозначным (или сущственно неоднозначным), если он не порождается никакой однозначной КС-грамматикой. С первого взгляда не видно, существуют ли вообще неоднозначные КС-языки, но нашим следующим примером и будет как раз такой язык. Проблема, .порождает ли данная КС-грамматика однозначный язык (т. е. существует ли эквивалентная ей однозначная грамматика), на самом деле неразрешима, но для некоторых больших подклассов КС-языков известно, что они однозначны; все придуманные до сих пор языки программирования тоже однозначны. Важнее всего то, что, как мы увидим в гл. 8, каждый детерминированный КС-язык оире-деляетсяоднозначной КС-грамматикой.

Пример 2.47. Пусть L~{abh\i j или / = /}. Этот КС-язык неоднозначен. Интуитивно это объясняется тем, что цепочки с i==l должны порождаться группой правил, отличных от правил, поролдающнх цепочки с i = По крайней мере некоторые нз цепочек с i~j = l должны порождаться обоими механизмами.

Одна из КС-грамматик, порождающих L, такова:

S-AB\DC А~аА\е В-ЬВс\е

D-aDb\e

Ясно, что она неоднозначна.

С помощью леммы Огдена можно показать, что язык L неоднозначен. Пусть G - произвольная КС-граМматика, порождающая L, и /е-число, связанное с G (см. теорему 2.24). Можно считать, что /гЗ. Рассмотрим" цепочку z = abc+}\ в которой выделены все символы а. Ее можно записать в виде z = uuwxy. Так "как w содержит выделенные позиции, то и и v состоят только из символов а. Если х содержит два различных символа, то, конечно, uvwxyL, так что либо ха*, либо л: Ь*, либо хе*.

Если то цепочка uuwxy имеет вид для

некоторого lp/e и потому не принадлежит L. Если-хс*, то uv-wxy имеет вид apifov++p, где, ipk. Эга цепочка тоже не принадлежит L.

Если xi?*, то auwxy = a-Pb-pc+\ где lpk. Если эта цепочка принадлежит L, то либо р - р, либо рфр и p - k\. В последнем случае цепочка wuK.i.vf/- a+2pfc+2pi,(;;+ft- конечно, не принадлежит L. Поэтому заключаем, что рр. Заметим, что pj = \v\ w р.=\х\.

По теореме 2.24 для любого /пО найдется вывод

(2.6.1) 5 => WЛf/ ->Wv"AxHjuu"wx"y

Пусть, в частности, fn = k\/p. Так как 1</Ji<ft, то т - целое число. Тогда wwxy = а+Ьс+-.

Для цепо*1ки а--Ьс можно показать по симметрии, что существуют н,, у, ffii, Ху, уу, где только Uy содержит символ а, £6*, и что найдется такой нетерминал В, что

(2.6.2) S=>+ иВу=> uv"Bxfy

ио"1тх"у = abk-

Если мы сумеем показать, что этим двум выводам цепочки Qk+k\ijk-vk\.k-vk\ соответствуют разные деревья, то тем самым докажем, что L - неоднозначный язык, поскольку грамматнка 0 была выбрана произвольно и оказалась неоднозначной.

Допустим, что выводам (2.6.1) и (2.6.2) соответствует одно и то же дерево. Так как Л порождает цепочки из символов а Ь, а В порождает цепочки из символов b и с, то А (соответственно В) не может быть меткой вершины, которая является

ул. . элМЁнШ Теории зык&б

потомком вершины, помеченной В (соответственно Л). Следовательно, найдется выводимая цепочка tAtBtay где t, t, t - терминальные цепочки. Для всех i и / цепочка t-vwxtv{wxlt должна по предположению принадлежать L. Но \v\\x\ и lillxil и, кроме того, X м состоят только из символов &, V-из символов а и - из символов с. Тогда, выбрав i и / равными, и достаточно большими, можно считать, что в соответствующей цепочке символов Ь больше, чем символов а или с. Отсюда заключаем, что грамматика О неоднозначна, а стало быть, и язык L неоднозначен. □

УПРАЖНЕНИЯ

2.6.1. Пусть КС-язык и -регулярное множество Пока жите, что следующие языки контекстно-свободны*

(а) INIT(L);

(б) FIN(L);

(в) SUB(L);

(г) LIR\

(д) L{\R.

Определения операций (а) -(г) даны перед упр. 2.3.17.

2.6.2. Покажите, что если Л - КС-язык и h - гомоморфизм, то h~(L) - КС-язык. Указание; Пусть Р-МП-автомат, допускающий L. Постройте МП-автомат Р\ который применяет h по очереди к каждому входному символу, запасает результат в буфере управляющего устройства и моделирует Р на символах из буфера. Позаботьтесь о том, чтобы Ваш буфер был конечной длины.

2.6.3. Покажите, что следующие языки не контекстно-свободны:

(а) {WЬc\ii}\

(б) \aW\i<i<k}\

(в) множество цепочек с одинаковым числом символов а, & и с;

(г) {аУа¥\11}\

(д) {«";7"rt"m, п> l);

(е) {aVc* I все числа t, /, k разные};

(ж) {пНа \ -число в десятичной записи]-. (Эта конструкция представляет холлеритовы поля в Фортране.)

**2.6.4. Покажите, что каждый КС-язык в однобуквенном алфавите регулярен. Указание: Воспользуйтесь леммой о разрастании.

**2.6.5. Покажите, что следующие хезыки не всегда являются КС-языками, когда L-КС-язык:

упражнения

(а) МАХ (L);

(б) МШ(Р);

(в) Lf = {х\ху для некоторого у и л: = г/}.

*2.6.6. Докажите следующую лемму о разрастании для линейных языков. Если L-линейный язык, то найдется такая константа k, что если zL я \ z\k, то z = uvwxy, где uvxy \k, ьхфе и uv%xyL для всех i.

2.6.7. Покажите, что язык {a"b"a"b"\n, 1} не линейный.

*2.6.8. МП-автоматом с одним поворотом называется МП-автомат, который для любой входной цепочки сначала только пишет в магазин, а потом только стирает, т. е. начав стирать символы в магазине, он уже не может снова записывать (это и есть один поворот в работе с магазином). Покажите, что КС-язык линеен тогда и только тогда, когда он распознается МП-автоматом с одним поворотом.

*2.6.9. Пусть G-=(N, S, Р, 5) -КС-грамматика. Покажите, что следующие языки контекстно-свободны:

(а) {а I 5 =>;«!;

(б) {a\S=;ay,

(в) {а5=*а}.

2.6.10. Дайте подробное доказательство следствия из теоремы 2.25.

2.6.11. Дополните доказательство теоремы 2.26.

2.6.12. Дайте более формальное описание ДМП-автоматов, фигурирующих в доказательствах лемм 2.29(1) и 2.30(1).

*2.6.13. Покажите, что язык QcHPc из разд. 2.6.3 контекстно-свободен тогда и только тогда, когда он пуст.

2.6.14, Покажите, что следующие проблемы для кс-грамматик О неразрешимы:

(а) е(0)-кс-язык?

(б) P(G) -регулярный язык?

(в) P(G)-детерминированный кс-язык?

<Указание: Используйте упр. 2.6.13 и рассмотрите кс-грамматику для языка QcDPc.

2.6.15. Докажите, что проблема, порождает ли контекстно-зависимая грамматика кс-язык, неразрешима.

гтт,,** Усть Gj и G„ -кс-грамматнки. Докажите неразрешимость проблемы „L{G,)f]L{G,) = 0?" *2 6 17 ТТ

к.о,/ Уь 1 -кс-грамматика и Gg -праволинейная грамматика. Докажите