2.4.16. Преобразуйте следующие грамматики к нормальной форме Хомского:

(а) 5051101

(б) S-aB\bA A-aS\bAA\a B~bS\aBB\b

2.4.17. Если G-(N, 2, Р, S) -грамматика в нормальной форме Хомского, 5=, 11" " wZ*, то каково ft?

2.4.18. Дайте подробное доказательство теоремы 2.17.

2.4.19. Преобразуйте к нормальной форме Грейбах грамматику

S-BolAb . А -Sa\AAb\a BSb\BBa\b

используя

(а) алгоритм 2.14,

(б) алгоритм 2.15.

*2.4.20. Постройте быстрый алгоритм, проверяющий, леворекурсивна ли КС-грамматика G.

2.4.21. Постройте быстрый алгоритм, устраняющий в КС-грамматнке правую рекурсию.

2.4.22. Дополните доказательство леммы 2.15. *J.4.23. Докажите леммы 2.17-2.19.

2.4.24, Завершите преобразования примера 2.30 и получите приведенную грамматику в нормальной форме Грейбах.

2.4.25. Сравните относительные достоинства алгоритмов 2.14 и 2.15, особенно с точки зрения объема результирующей грамматики.

*2.4.26. Покажите, что кандай КС-язык, не содержащий пустой цепочки е, определяется грамматикой, все правила которой имеют вид А-аВС, А~аВ или А-а.

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

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

*2.4.28. Покажите, что каждый КС-язык порождается грамматикой, все правила которой имеют вид А-аВЬС, А--аВЬ,

> аВ или А е.

а. Если e£L(G), то допускается еще правило

**2.4.29. Рассмотрим грамматику с двумя правилами 5-55а. Покажите, что число Х„ различных левых выводов цепочки а" находится из соотношения

i-hi-n i ф О /0

2п\ \п j

где Xi=l. Покажите, что

(числа такого вида называются числами Каталана),

*2.4.30. Покажите, что КС-язык L, не содержащий цепочек, длина которых меньше 2, порождается грамматикой с правилами вида А->ааЬ.

2.4.31. Покажите, что каждый КС-язык определяется грамматикой, удовлетворяющей условию: если ... Х-правая часть правила, то все Х, ..., X;; различны.

Определение. КС-грамматика G-(N, S, Р, S) называется ли-нейной, если каждое ее правило имеет вид Л -цВл: или Л-уш, где В N, а ш и л: принадлежат 2*.

2.4.32. Покажите, что каждый линейный язык, не содержащий пустой цепочки, определяется грамматикой, все правила которой имеют вид А-аВ, А~Ва илн А-а.

*2.4.33. Покажите, что каждый КС-язык определяется такой грамматикой G = (N, 2, Р, 5), что если Л 6 N-{5}, то язык {даЛ=Ф*Е н ixii;*} бесконечен.

2.4.34. Покажите, что каждый КС-язык определяется рекурсивной грамматикой. Указание: Используйте лемму 2.14 и упр. 2.4.33.

*2.4.35. Назовем КС-грамматику G = (N, 2, Р, 5) квазилинейной, если для каждого правила А-Х- ... Xj существует не более Одного символа Х,-, порождающего бесконечное множество терминальных цепочек. Покажите, что каждая квазилинейная грамматика порождает линейный язык.

Определение. Графом КС-грамматики G(N, 2, Р, S) назовем такой ориентированный неупорядоченный граф (N U 2 U {е}, R), что ARX тогда и только тогда, когда Л-аХр - правило грамматики для некоторых аир.

2.4.36. Покажите, что если грамматика не содержит бесполезных символов, го все вершины ее графа достижимы из 5. Верно ли обратное утверждение?

2.4.37. Пусть Т - преобразование КС-грамматик, определенное в лемме 2.14, т. е. Т отображает 6 в G, где G и G - грамматики из леммы 2.14. Покажите, что алгоритмы 2. Ш и 2. И можно реализовать повторными применениями преобразования Т.

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

2.4.38. Постройте программу, устраняющую в КС-грамматике бесполезные символы.

2.4.39. Постройте программу, которая преобразует КС-грамматику в эквивалентную приведенную КС-грамматику.

2.4.40. Постройте программу, устраняющую в КС-грамматике левую рекурсию.

2.4.41. Постройте программу, которая решает, является ли данное дерево деревом вывода в КС-грамматике,

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

Дерево вывода имеет немало других названий, среди которых: дерево порождения, диаграмма разбора, дерево разбора, дерево анализа, синтаксическое дерево, дерево составляющих. Аналогичное понятие хорошо известно в лингвистике. Понятие левого вывода появилось в работе Эви [1963].

Многие алгоритмы этой главы были известны еще в начале 1960-х годов, хотя часть из них появилась в литературе значительно позже. Теорема 2,17 (нормальная форма Хомского) впервые доказана Хомским [ 1959а]. Теорема 2.18. (нормальная форма Грейбах) впервые доказана Грейбах [I965J. Алгоритм 2.15 и результат, сформулированный вупр. 2.4.30, принадлежат Розенкранцу [1967]. Алгоритм 2.14 приписывают М. ГГаулу.

Представление КС-языков с помощью систем уравнений использовалось в работах Хомского [1963], Хомского и Шютценберже [1963], Гинзбурга и Раиса [1962].

Операторные грамматики впервые рассмотрены Флойдом [1963]. Нормальные формы, приведенные в упр. 2.4,26 - 2.4.28, были получены Грейбах[1965],

2.5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

Теперь мы введем понятие автомата с магазинной памятью - тип распознавателя, представляющий собой естественную модель синтаксических анализаторов контекстно-свободных языков. Автомат с магазинной памятью - это односторонний недетерминированный распознаватель, в потенциально бесконечной памяти которого элементы информации хранятся и используются так же, как патроны в магазине автоматического орулия, т. е. в каждый момент доступен только верхний элемент магазина. Распознаватель этого типа изображен па рис. 2.15.

Мы докажем один фундаментальный результат, относящийся к автоматам с магазинной памятью, а именно: язык контекстно-свободен тогда и только тогда, когда он допускается недетерминированным автоматом с магазинной памятью. Рассмотрим также

Входная тнта (ттдко читать)

управляющее уетрейвтдо с конечной памятью

магаэим

Рис. 2.15. Автомат с магазинной памятью;

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

2,5.1. Основное определение

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

Определение. Автомат с магазинной памятью (сокращенно МП-автомат)-это семерка

P-(Q, 2, Г, б, q,, Zo, F)

(1) Q-конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства;

(2) 2 - конечный входной алфавит;

(3) Г-конечный алфавит магазинных символов.

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

2.5. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

(4) б-отображение множества Qx{Su{})xr в множество конечных подмножеств множества QxT*;

(5) QqQ-начальное состояние управляющего устройства;

(6) 2ц Г-символ, находящийся в магазине в начальный момент (начальный символ);

(7) FQ-множество заключительных состояний.

Конфигурацией МП-автомата Р называется тройка {q, а) € Qx2*xr*, где

(1) q-текущее состояние управляющего устройства;

(2) W-неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w~e, то считается, что вся входная лента прочитана;

(3) а-содержимое магазина; самый левый символ цепочки а считается верхним символом магазина; если а = е, то магазин считается пустым.

Такт работы МП-автомата Р будем представлять в виде бинарного отношения [-р (или -, когда Р подразумевается), определенного на конфигурациях. Будем писать

(2.5.1) [q, aw, Za)\~{q, w, уа)

если лножество b{q, а, Z) содержит [q\ у), где q, q Q, a£2\j{e\, we2\ и а, у£Г\

Если афе, то (2.5.1) говорит о том, что МП-автомат Р, находясь в состоянии q и имея а в качестве текущего входного символа, расположенного под входной головкой, а Z-в качестве верхнего символа магазина, может перейти в новое состояние q, сдвинуть входную головку на одну ячейку вправо и заменить верхний символ магазина цепочкой у магазинных символов. Если у = е, то верхний символ удаляется из магазина, и тем самым магазинный список сокраиается.

Если а = е, будем называть этот такт е-тактом. В е-такте текущий входной символ не принимается во внимание и входная головка не сдвигается. Однако состояние управляющего устройства и содержимое памяти могут измениться. Заметим, что (?-такт может происходить и тогда, когда вся входная цепочка прочитана.

Следующий такт невозможен, если магазин пуст.

Можно обычным образом определить отношения -для /0, I-* и (-+ , а именно: -* и (-- это соответственно рефлексивно-транзитивное и транзитивное замыкания отношения j-.

Начальной конфигурацией МП-автомата Р называется конфигурация вида (0, W, Zf,), где ш2*, т. е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только

начальный символ Z. Заключительная конфигурация-это конфигурация вида {q,e,a), где qF и аТ*.

Говорят, что цепочка w допускается МП-автоматом Р, если (ц, W, Zo)H*(?» . ct) некоторых qF иаГ*. Языком, определяемым (или допускаемым) автоматом Р (обозначается L (Р)), называют множество цепочек, допускаемых автоматом Р,

Пример 2.31. Построим МП-автомат, определяющий язык L={0"l"\nQ}. Пусть Р = ({(7о, <7i, qj, {О, 1}, {Z, 0\,6,q,,Z, {q,}), где

6(0. О, Z) Uq,, QZ)\ б(?1, О, 0) ={{q,, 00)} б(?1, 1, 0) \{q,, е)\ б(?„ 1, 0) -{(?,, е)\ 6(2, Z) ={(0, е)}

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

(?о. ООП, Z)i-te, on, OZ)

b(?t, П, OOZ) l-(9., h OZ) l-(?2» Z)

Вообще можно показать, что

(?о. О, Z)Ь (?„ е, 0Z) („ 0 OZ)H"t?i. 0Щ {q„ 1, 0Z)\~iq„ е, OZ) (9„ 1, 0Z)H(., Z) (?2 б. 2)- (?о, е, е)

Объединяя все это, получаем для 1

(q,, 0"1", Z)l-2«x(, е, е)

{q,, е, Z)h(o. 2)

Таким образом, LL{P).

Покажем, что LL{P), т. е. что Р допускает только цепочки вида 0"1". Эта часть доказательства труднее. Обычно легче доказать, что такие-то цепочки распознаватель допускает, и так