2.5.23. Существует ли КС-язык, который не допускается 2ДМП-автоматом?

Упражнения на програлширование

2.5.24. Напишите программу, моделирующую детерлшниро-вапный МП-автомат.

*2.5.25. Придумайте язык программирования, пригодный для задания МП-автоматов. Постройте компилятор для Вашего языка. Исходная программа в этом языке должна определять МП-автомат Р. Объектная программа должна описывать распознаватель, разумным способом моделирующий поведение Р на входных цепочках W.

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

Замечания по литературе

Важность магазинов (известных также под названием стеков) в процессах обработки языков была осознана в начале J950-x годов. Эттиигер [I96I] и Шютценберже [1963] первыми формализовали понятие автомата с магазинной памятью. Эквивалентность МП-автоматов и КС-грамматик была показана Хомским [1952] и Эви [1963].

Двусторонние МП-автоматы изучались Хартманнсом и др. [19G5], Грэем и др. [1967], Ахо и др. [1968]. Куком [1971].

2.6. СВОЙСТВА КОНТЕКСТНО-СВОБОДНЫХ ЯЗЫКОВ

В этом разделе мы исследуем некоторые из основных свойств КС-языков. Упоминаемые здесь результаты на самом деле образуют малую долю огромного богатства знаний о КС-язьтках, В частности, мы рассмотрим некоторые операции, относительно которых замкнут класс КС-языков, некоторые результаты о разрешимости и кое-что о неоднозначных КС-грамматиках и языках.

2.6.1, Лемма Огдена

Начнем с доказательства одной теоремы (леммы Огдена) о КС-грамматиках, из которой можно будет извлечь ряд результатов о КС-языках и, в частности, „лемму о разрастании" для КС-языков.

Определение. Позицией в цепочке длины k назовем такое целое число i, что l<i<A. Будем говорить, что символа занимает позицию i (или i-ю позицию) в цепочке если wwaw и \ w\ = 1 - Например, символ а занимает третью позицию в цепочке Ьаасс.

Теорема 2.24. Для каждой КС-грамматики G -(N, 2, Р, S)

существует такое целое число к;г\, что если zL(G), \z\k и в цепочке z выделены к или более различных позиций то z моото записать в виде uvwxy, причем

(1) W содержит хотя бы одну выделенную позицию;

(2) либо и и V обе содержат выделенные позиции, либо хиу обе содержат выделенные позиции;

(3) VWX содержит не более к выделенных позиций;

(4) существует такой нетерминал Л, что

St}tiAyzluvAxyl ... =>JuLJxi/=>JwuWy для всех t>0 (в случае i = 0 вывод имеет вид S =иЛуzuwy).

Доказательство. Пусть m =}i=N и /-длина самой длинной из правых частей правил множества Р. Выберем А л+з и рассмотрим дерево вывода Т некоторой цепочки 2Р(0),где Пусть в цепочке z выделены по крайней мере к позиций. Заметим, что Т должно содерлать хотя бы один путь длины, не меньшей 2т-ЬЗ. Выделим листья дерева Т, которые в кроне z дерева Т занимают выделенные позиции.

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

Построим путь Hi, п, ... в дереве Т следующим образом:

(1) nj -корень дерева Т;

(2) если мы нашли п,- и только один прямой потомок этой вершины имеет выделенные листья среди своих потомков (т. е. Hi-неветвящаяся вершина), то возьмем в качестве n+j этого прямого потомка;

(3) если Hi - ветвящаяся вершина, то выберем в качестве того прямого потомка вершины п,-, который имеет среди своих

потомков наибольшее число выделенных листьев (если таких прямых потомков несколько, выберем самый правый, но можно взять и любой);

(4) если Hi-лист, то путь окончен.

Пусть п, «з, /г, -путь, построенный описанным способом. Простой индукцией по i можно показать, что если среди вершин Hj, Hi есть г ветвящихся, то/г,+1 имеет по крайней мере /ая+з-г выделенных потомков. Базис, г = О, тривиален: г -О и имеет по крайней мере/с = " выделенных потомков. Для доказательства шага индукции заметим, что если п-неветвящаяся вершина, то п и /г/ имеют одно и то же число выделенных потомков, и что если /г/ - ветвящаяся вершина, то имеет по крайней мере (1 )" часть выделенных потомков вершины П;.

Так как имеет 1" выделенных потомков, то путь .. .,Пр содержит по крайней мере 2/п + З ветвящихся вершин. Кроме того, Пр - лист, и потому он не является ветвящейся вершиной. Следовательно, р>2т + 3.

Пусть bj, b., .. ., brnv - это последние 2m+ 3 вершины, принадлежащие пути П], Пр. Назовем bi левой ветвящейся вершиной, если прямой потомок вершины 6/, не принадлежащий этому пути, имеет выделенного потомка слева от Пр. В противном случае будем называть Ь[ правой ветвящейся вершиной.

Предположим, что по крайней мере m + 2 вершины из &1, &2т+з левые ветвящиеся. Случай, когда по крайней мере т-\-2 вершины правые ветвящиеся, исследуется аналогично.

Рнс. 2.17. Дерево вывода Т.

Пусть /j, ••> - последние т-\-2 левые ветвящиеся вершины последовательности fe, tg/n+s Так как 41=Nm,

то среди можно найти две вершины, скажем If и

Ig, с одной и той же меткой, скажем Л, и f<g. Эта ситуация изображена на рис. 2.17. Двойной линией показан путь/г, .. .,Пр, звездочки указывают выделенные листья (кроме этих могут быть и другие).

Если удалить всех потомков вершины 1р то получится дерево вывода с кроной иАу, где и состоит нз листьев, расположенных слева от Ij, а у-яз листьев, расположенных справа. Таким образом, 5 z>+ ыАу. Если мы рассмотрим поддерево с корнем If, из которого удалены потомки вершины то увидим, что Л=+уЛх, где V я х-части кроны этого поддерева, состоящие из листьев, расположенных соответственно слева и справа от L. Наконец, пусть tc-крона поддерева с корнем 1. Тогда Л W и, значит, z = uvwxy.

Объединяя эти выводы, получаем S z иАу uwy и для всех i 1

5 z>+ uAyz- uuAxy=> uvAxyz- . . uvAxyz uuwxy

Таким образом, условие (4) выполнено. Кроме того, цепочка и имеет хотя бы одну выделенную позицию, которую занимает потомок некоторого прямого потомка вершины 1-. Аналогично цепочка и имеет хотя бы одну выделенную позицию, которую занимает потомок вершины If. Следовательно, условие (2) тоже выполнено. Условие (1) выполняется потому, что цепочка w имеет выделенную позицию, а именно ту, которую занимает Пр.

Чтобы проверить выполнение условия (3), состоящего в том, что цепочка uwx имеет не более г выделенных позиций, заметим, что цепочка Ь, будучи (2т+ 3)-й ветвящейся вершиной от конца пути /ij, Пр, имеет не более к выделенных позиций. Так

как If - потомок вершины Ь, отсюда непосредственно следует нужный результат.

Надо было бы рассмотреть еще противоположный случай, когда по крайней мере т-\-2 вершин из Ь, Ь правые ветвящиеся. Однако здесь можно рассуждать по симметрии, и в итоге мы обнаружим, что условие (2) выполняется, так как каждая из цепочек х я у имеет выделенные позиции. □

Докажем важное следствие леммы Огдена, которое иногда называют леммой о разрастании для КС-языков.

Следствие. Пусть L - КС-язык. Тогда существует такая константа к, что если \ г\к и zL, то г можно представить в виде Z = uvwxy, где vx Ф е, \ uwx \к и uuwxy £ L для всех i 0.

Доказательство. В теореме 2,24 взять какую-нибудь КС-грамматнку для языка L и считать все позиции во всех цепочках выделенными. □

Именно этим следствием из теоремы 2.24 мы будем чаще всего пользоваться при доказательстве того, что некоторые языки не контекстно-свободны. Самой теоремой 2.24 мы воспользуемся, когда в разд. 2.6.5 речь пойдет о существенной неоднозначности КС-языков.

Пример 2.38. С помощью леммы о разрастании покажем, что язык L = {a"- /г1} не является КС-яэыком. Если бы он был КС-языком, то нашлось бы такое число к, что если пк, то auuwxy, где цепочки и я х ие могут быть обе пустыми и \vwx\k. Пусть, в частности, nk. Так как kk, то по предположению uvwxy € L. Но так как шх А, то \ \ux\k и ft- < I uvwxHj] ft- + ft. Заметим, что следующий после ft квадрат целого числа - число (ft + 1)- = ft + 2ft + I. Так как

й + й < г-j-2/e -- ], ТО I uvwxy] не равно квадрату целого числа. Но по лемме о разрастании uvwxyL; получили противоречие.□

Пример 2.39. Покажем, что язык L = {a"h"c"1} - не КС-язык. Если бы он был КС-языком, то мы взяди бы константу k, которая определяется в лемме о разрастании. Пусть z=aVc, Тогда z = uvwxy. Так как \ vwx\ky то в цепочке uwx не могут быть вхождения каждого из символов а, h и с. Таким образом, цепочка uwy, которая по лемме о разрастании принадлежите, содержит либо k символов а, либо k символов с. Но она не может иметь k вхождений каждого из символов а, h и с, потому что \ uwy\ <Ck, Значит, вхождений какого-то из этих символов в uwy больше, чем другого, и, следовательно, uwyL. Полученное противоречие позволяет заключить, что L - не КС-язык. □

2.6.2. Свойства замкнутости класса КС-языков

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

Определение. Пусть - класс языков и язык LS* принадлежит Допустим, что 2 {1, ..., а„} и языки La, . . La

принадлежат . Класс замкнут относительно подстановки, если для любого набора языков l, Lq, ..., La язык

принадлежит

Пример 2.40. Пусть Л={0«1"1л> i}, Z.o={4 HLj = {b"c"m>l}. Тогда результатом подстановки языков к ъ язык L будет язык

L = {a"b"c"bV.. ,b">c""\n 1, 1} □

Теорема 2.25, Класс КС-языков замкнут относительно подстановки»

Доказательство. Пусть L 2*-КС-язык и 2 = {а, .. а,}. Пусть 2* -КС-язык для каждого а 2 и L -результат подстановки языков вместо а в цепочки языка L. Пусть G == (N, 2, Pt 5) -КС-грамматика языка L и Go = (No, 2, Я, а) -

КС-грамматика языка L. Предполагаем, что N и все N« попарно не пересекаются. Возьмем С -(N, 2, Р\ 5), где

(1) N=11 N,UN;

(2) 2= и 2,;

(3) пусть h - гомоморфизм, определенный на N1)2 и такой, что h(A)A для всех АН и h{a) = a для tzG2; положим

Р = {A-h{a)\Aa.P}\ U Р.

Итак, Р состоит из правил всех грамматик Ga и правил трамматики G, в которых все терминалы сделаны нетерминалами со штрихами. Пусть aj.. MjL н xL. для Xik. Тогда

5 =G . - и] =G xai.. .a} -rb • • =G x. . .x. Следовательно, UL{G).

Допустим, что wL{G), и рассмотрим дерево вывода Т цепочки ш. Так как N и N не пересекаются, каждый лист с меткой, отличной от е, имеет по крайней мере одного предка, помеченного а, где а 2. Если удалить нз Т каждую вершину, у которой есть предок, отличный от нее и помеченный а для 2, то получим дерево вывода Т с кроной а}.. .а], где Uj... ajL. Если Xi - крона поддерева дерева Т, над которыми доминирует /-Й лист, дерева Т", то wx.. .Xf и xL Таким образом, L{G) = L (G). □

Следствие, Класс КС-языков замкнут относительно {]) объединения, (2) конкатенации, (3) итерации, (4) позитивной итерации и (5) гомоморфизма.

Доказательство. Пусть и - КС-языки.

(1) Подставим вместо а н вместо b в КС-язык {а, Ь),

(2) Подставим вместо а и Ц вместо b ъ {а Ь}.

(3) Подставим вместо а ъ а*.

(4) Подставим вместо а в G+.

(5) Для гомоморфизма h возьмем ~ {h [а)} и, подставив Дд вместо а в L, получим Л(Р). П

Теорема 2.26. Класс КС-языков замкнут относительно пересечения с регулярными множествами.

Доказательство. Нетрудно показать, что МП-автоматР и параллельно работающий конечный автомат А можно моделировать подходящим МП-автоматом Р. Этот составной МП-автомат Р прямо моделирует Р и изменяет состояние автомата А

8 А. Ахо, Дж. Ульман, т. 1