Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
Заключение. Рассмотрим абстрактный набор, состоящий из словарей Ve, Vm и множества команд
(?-*^, x1)).
') Строго говоря, этот факт нуждается в доказательстве; оно, однако, очень просто и может быть предоставлено читателю. — Прим. ред. Глава IX. Автомати с магазинной памятью
151
Можно с равным успехом говорить, что абстрактный автомат, определяемый этим набором, допускает или порождает некоторый язык.
§ 9.3. КЛАСС ЯЗЫКОВ, ДОПУСКАЕМЫХ (ПОРОЖДАЕМЫХ) МП-АВТОМАТАМИ
9.3.1. МП-автомат, допускающий КС-язык
Сейчас мы покажем, что по всякой КС-грамматике можно построить МП-автомат, допускающий (порождающий) язык L(G). Рассмотрим КС-грамматику G:
^-М, I i<i<4 Vr = Wi I !</<"};
аксиома: S = Ai; Ai„ ..., At-Xaltk ,
Cj '.
1 ^ і ^ m
Построим по этой грамматике МП-автомат. Его входным словарем Ve будет Vt, дополненный символом е\ словарем Vm— объединение Vt U Va, дополненное символами о и е; его состояниями будут символы [0], [1], [А], ..., [Am]. Состояние [0] будет начальным. Состояние [1] мы назовем «досинтаксическим», состояния [Ai] — «синтаксическими».
Список команд автомата включает:
1. Начальную команду
(е, [0], о)->([ 1], S).
2. Команды перехода в синтаксическое состояние
(е, [1], A1)-+([A1), а);
число этих команд равно числу синтаксических состояний (т. е. числу вспомогательных символов грамматики G).
3. Команды порождения (или допускання)
(е, [A1], *)->([1], шг, kl),
число которых равно числу правил исходной грамматики.
4. Команды чтения или копирования символов
(ah [1], а,)->([1], а), число которых равно числу терминальных символоэ. 152
Часть II. Некоторые замечательные классы языков
5. Заключительную команду
(е, [1], а) -> ([0], а).
Функционирование автомата при порождении Пусть нашему автомату заданы правильные начальные условия; тогда он переходит в досинтаксическое состояние [1], записывает на рабочей ленте аксиому, запоминает ее, т. е. переходит в соответствующее синтаксическое состояние, и одновременно стирает аксиому.
Находясь в синтаксическом состоянии [Л,-], автомат выбирает некоторое правило A-* wi,h, записывает его правую часть на рабочей ленте, устанавливает рабочую головку так, чтобы она обозревала последний записанный ею символ, и возвращается в досинтаксическое состояние [1].
Вообще, если автомат читает на рабочей ленте M левую часть некоторого правила, то он стирает ее, переходит в соответствующее синтаксическое состояние, записывает на M правую часть того же правила и, вернувшись в досинтаксическое состояние, обозревает последний символ, записанный им на М.
Если же автомат читает на ленте M терминальный символ, то он стирает его, предварительно скопировав на ленте Е.
Процесс заканчивается, когда автомат после очередного копирования обозревает символ ст — самый левый символ на ленте М. Ясно, что описанный процесс эквивалентен построению вывода в КС-грамматике с копированием полученных терминальных символов (правда, в обратном порядке).
Функционирование автомата при допусканий. Функционирование автомата при допусканий (быть может, интуитивно несколько менее ясное) гарантируется «обратимостью» МП-автоматов.
Замечание. Рассматриваемый МП-автомат является недетерминированным. Заметим, однако, что в его командах состояние [Л;] может встретиться в правой части лишь в случае, когда в левой есть Ai. Таким образом, переход в синтаксическое состояние всегда детерминирован.
Пример. Построим описанным только что способом МП-автомат для языка Lm и сравним его с автоматом, рассмотренным выше, в п. 9.1.3.
Пусть имеется КС-грамматика со словарями
VA = {S), Vr = {а, Ь, с}
и правилами
§-*aSa, S-*bSbx S-*c, Глава IX. Автомати с магазинной памятью
153
Поскольку в этой грамматике имеется ровно один вспомогательный символ — аксиома S, наш автомат будет иметь только одно синтаксическое состояние. Вот программа автомата, соответствующего данной грамматике:
1: (е, [0], cr)-> ([1], S)
2: (е, [1], S)-*([S], а)
([1], aSa)
3: (е, [S], е)-*{ ([1], bSb)
(ІП, с)
4: (а, [II, а) (Ь, [1], Ь)
(с, [1], с) 5: (е, [11, о)-
(Ulo)
¦([01, о).
Этих команд оказывается меньше, чем команд, приведенных в п. 9.1.3, поскольку последние были детерминированными (они предназначались для допускання цепочек). Читателю будет полезно исследовать, как новые команды связаны со старыми.
9.3.2. Грамматика, порождающая язык, допускаемый МП-автоматом
Построение КС-грамматики, порождающей язык, допускаемый заданным МП-автоматом, также возможно, однако выполняется значительно более сложным способом. В частности, для этого необходима предварительная «нормализация» команд автомата. Здесь мы' примем на веру утверждение о возможности такого построения (набросок доказательства дан ниже, в § 15.3). Таким образом, имеет место следующая
Теорема. Класс языков, допускаемых (порождаемых) МП-автоматами, совпадает с классом КС-языков (см. ниже, § 15.3).
9.3.3. Упражнения
1. Пользуясь методом п. 9.3.1, построить МП-автомат, допускающий «бесскобочный язык», порождаемый следующей грамматикой:
