ГЛАВА 6

Автоматы с магазинной памятью

Контекстно-свободные языки задаются автоматами определенного типа. Такой автомат называется автоматом с магазинной памятью, или магазинным автоматом, и является расширением недетерминированного конечного автомата с f-переходами, представляю­щего собой один из способов определения регулярных языков. Магазинный автомат — это, по существу, е-НКА с добавлением магазина. Магазин может читаться, в его верши­ну могут добавляться (заталкиваться, помещаться, заноситься) или с его вершины могут сниматься символы точно так же, как в структуре данных типа «магазин».

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

6.1. Определение автоматов с магазинной памятью

В этом разделе магазинный автомат представлен сначала неформально, а затем — как формальная конструкция.

6.1.1. Неформальное введение

Магазинный автомат — это, по существу, недетерминированный конечный автомат с £-переходами и одним дополнением — магазином, в котором хранится цепочка «магазинных символов». Присутствие магазина означает, что в отличие от конечного ав­томата магазинный автомат может «помнить» бесконечное количество информации. Од­нако в отличие от универсального компьютера, который также способен запоминать не­ограниченные объемы информации, магазинный автомат имеет доступ к информации в магазине только с одного его конца в соответствии с принципом «последним пришел — первым ушел» («last-in-first-out»).

Вследствие этого существуют языки, распознаваемые некоторой программой компь­ютера и нераспознаваемые ни одним магазинным автоматом. В действительности, мага­зинные автоматы распознают в точности КС-языки. Многие языки контекстно-свободны, включая, как мы видели, некоторые нерегулярные, однако существуют языки, которые просто описываются, но не являются контекстно-свободными. Мы увидим это в разде­ле 7.2. Примером такого языка является {0ⁿl»2ⁿ | п > 1}, т.е. множество цепочек, состоя­щих из одинаковых групп символов 0, 1 и 2.

	Конечное управление

Вход

Допустить/отвергнуть

Магазин

Рис. 6.1. Магазинный автомат как конечный автомат с магазинной структурой данных

Магазинный автомат можно рассматривать неформально как устройство, представ­ленное на рис. 6.1. «Конечное управление» читает входные символы по одному. Мага­зинный автомат может обозревать символ на вершине магазина и совершать переход на основе текущего состояния, входного символа и символа на вершине магазина. Он мо­жет также выполнить «спонтанный» переход, используя е в качестве входного символа. За один переход автомат совершает следующие действия.

1. Прочитывает и пропускает входной символ, используемый при переходе. Если в ка­честве входа используется Е, то входные символы не пропускаются.
2. Переходит в новое состояние, которое может и не отличаться от предыдущего.
3. Заменяет символ на вершине магазина некоторой цепочкой. Цепочкой может быть £, что соответствует снятию с вершины магазина. Это может быть тот же символ, ко­торый был ранее на вершине магазина, т.е. магазин не изменяется. Автомат может заменить магазинный символ, что равносильно изменению вершины без снятий и за­талкиваний. Наконец, символ может быть заменен несколькими символами— это равносильно тому, что (возможно) изменяется символ на вершине, а затем туда по­мещаются один или несколько новых символов.

Пример 6.1. Рассмотрим язык L_mir = {ww^R | w е (0 + 1)*}. Этот язык образован па­линдромами четной длины над алфавитом {0, 1} и порождается КС-грамматикой (см. рис. 5.1) с исключенными продукциями Р —> 0 и Р —> 1.

Дадим следующие неформальное описание магазинного автомата, допускающего I ^[1]

1. Работа начинается в состоянии q₀, представляющем «догадку», что не достигнута сере­дина входного слова, т.е. конец слова vv, за которым должно следовать его отражение. В состоянии q₀ символы читаются и их копии по очереди записываются в магазин.
2. В любой момент можно предположить, что достигнута середина входа, т.е. конец слова w. В этот момент слово w находится в магазине: левый конец слова на дне ма­газина, а правый — на вершине. Этот выбор отмечается спонтанным переходом в состояние q,. Поскольку автомат недетерминирован, в действительности предпола­гаются обе возможности, т.е. что достигнут конец слова w, но можно оставаться в состоянии q₀ и продолжать читать входные символы и записывать их в магазин.
3. В состоянии q, входные символы сравниваются с символами на вершине магазина. Если они совпадают, то входной символ пропускается, магазинный удаляется, и ра­бота продолжается. Если же они не совпадают, то предположение о середине слова неверно, т.е. за предполагаемым w не следует w^R. Эта ветвь вычислений отбрасыва­ется, хотя другие могут продолжаться и вести к тому, что цепочка допускается.
4. Если магазин опустошается, то действительно обнаружен вход и>, за которым следу­ет w^R. Прочитанный к этому моменту вход допускается.

□

6.1.2. Формальное определение автомата с магазинной памятью

Формальная запись магазинного автомата (МП-автомата) содержит семь компонен­тов и выглядит следующим образом.

Р = (Q, 2, Г,5,q₀,Z₀,F) Компоненты имеют такой смысл.

Q: конечное множество состояний, как и у конечного автомата.

1: конечное множество входных символов, такое же, как у конечного автомата.

Г: конечный магазинный алфавит. Он не имеет конечноавтоматного аналога и явля­ется множеством символов, которые можно помещать в магазин.

8: функция переходов. Как и у конечных автоматов, 8управляет поведением автома­та. Формально, аргументами 8 являются тройки 8(q, а, X), в которых q — состояние из множества Q, а — либо входной символ, либо пустая цепочка £, которая, по пред­положению, не принадлежит входному алфавиту, X— магазинный символ из Г. Вы­ход 8 образуют пары (/;, у), где р — новое состояние, а у— цепочка магазинных символов, замещающая X на вершине магазина. Например, если у= е, то магазинный символ снимается, если у=X, то магазин не изменяется, а если у= YZ, то X заменя­ется на Z, и Y помещается в магазин.

q₀: начальное состояние. МП-автомат находится в нем перед началом работы.

Z₀: начальный магазинный символ («маркер дна»). Вначале магазин содержит только этот символ и ничего более.

F: множество допускающих, или заключительных, состояний.

Никаких «смешиваний и сочетаний»

В некоторых случаях МП-автомат может иметь несколько пар на выбор. Например, пусть 8(q, а,Х) = {(р, YZ), (г, £)}. Совершая переход, автомат должен выбрать пару целиком, т.е. нельзя взять состояние из одной пары, а цепочку для замещения в мага­зине — из другой. Таким образом, имея состояние q, символ X на вершине магазина и а на входе, автомат может либо перейти в состояние р и изменить X на YZ, перейти либо в г и вытолкнуть X. Однако перейти в состояние р и вытолкнуть X или перейти в г и изменить X на YZ нельзя.

Пример 6.2. Построим МП-автомат Р, допускающий язык L_m„ из примера 6.1. Вна­чале уточним одну деталь, необходимую для правильной организации работы с магази­ном. Магазинный символ Z₀ используется для отметки дна магазина. Этот символ дол­жен присутствовать в магазине, чтобы, удалив из магазина w и обнаружив на входе ww^R, можно было совершить переход в допускающее состояние q₂. Итак, наш МП-автомат для языка L_m„ можно представить в следующем виде.

Р = ({<7о, <7ь <?Л, {0. И, {0, 1, Z₀j, 8, Я01 Zo, Ш) Функция 5 определяется такими правилами.

1. 8(д₀, 0, Z₀) = {(<37,, OZo)} и b(q,_h 1, Z₀) = {(q₀, 1Z₀)}. Одно из этих правил применяется вначале, когда автомат находится в состоянии q₀ и обозревает начальный символ Z» на вершине магазина. Читается первый символ и помещается в магазин; Zo остается под ним для отметки дна.
2. 8(q₀, 0,0) ={(</„, 00)}, 8(qo, 0, 1) = {(q₀, 01)}, 8(qo, 1, 0) = {(q₀, 10)} и <5(^,1,1) = {(q₀, 11)}. Эти четыре аналогичные правила позволяют оставаться в состоянии q„ и читать входные символы, помещая каждый из них на вершину магазина над преды­дущим верхним символом.
3. S(qo, e, Z₀) = {(q,, Z₀)}, 5(q_lh e, 0) = {(q_h 0)} и 8{q₀, E, 1) = {(q,, 1)}. Эти правила по­зволяют автомату спонтанно (без чтения входа) переходить из состояния q₀ в со­стояние qi, не изменяя верхний символ магазина, каким бы он ни был.
4. 5{qi, 0, 0) = {(q_h e)} и <5(q_h 1,1)= {(qi, £)}. В состоянии q, входные символы прове­ряются на совпадение с символами на вершине магазина. При совпадении последние выталкиваются.
5. <5(<7/, е, Z₀) = {(<72, Z₀)}. Наконец, если обнаружен маркер дна магазина Z„ и автомат находится в состоянии q,, то обнаружен вход вида ww^R. Автомат переходит в со­стояние <72 и допускает.

□

6.1.3. Графическое представление МП-автоллатов

Функцию <5, заданную списком, как в примере 6.2, отследить нелегко. Иногда особен­ности поведения МП-автомата становятся более понятными по диаграмме, обобщающей диаграмму переходов конечного автомата. Введем в рассмотрение и используем в даль­нейшем диаграммы переходов МП-автоматов со следующими свойствами.

1. Вершины соответствуют состояниям МП-автомата.
2. Стрелка, отмеченная словом Начало, указывает на начальное состояние, а обве­денные двойным кружком состояния являются заключительными, как и у конеч­ных автоматов.
3. Дуги соответствуют переходам МП-автомата в следующем смысле. Дуга, отме­ченная а, XIа и ведущая из состояния q в состояние р, означает, что 5{q, а, X) со­держит пару (р, а) (возможно, и другие пары). Таким образом, отметка дуги пока­зывает, какой входной символ используется, а также, что было и что будет на вершине магазина.

Диаграмма не говорит лишь о том, какой магазинный символ является стартовым. По со­глашению им будет Zo, если не оговаривается иное.

• z₀/oz₀
• z₀/iz₀ 0,0/00 0,1/01

1,0/10          0,0/е

1,1/11           1,1/Е

Е, 0/0 е, 1/1 Рис. 6.2. Представление МП-автомата в виде обобщенной диаграммы переходов Пример 6.3. МП-автомат из примера 6.2 представлен в виде диаграммы на рис. 6.2. □

6.1.4. Конфигурации МП-автомата

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

Таким образом, конфигурация МП-автомата представляется тройкой (q, vv, у), где q — состояние, w— оставшаяся часть входа, у— содержимое магазина. По соглашению вершина магазина изображается слева, а дно — справа. Такая тройка называется конфи­гурацией МП-автомата, или его мгновенным описанием, сокращенно МО (instantaneous description — ID).

Поскольку МО конечного автомата— это просто его состояние, для представления последовательностей конфигураций, через которые он проходил, было достаточно ис-

Л

пользовать 8 . Однако для МП-автоматов нужна нотация, описывающая изменения со­стояния, входа и магазина. Таким образом, используются пары конфигураций, связи ме­жду которыми представляют переходы МП-автомата.

Пусть Р = (g, Г, 8, q₀, Z₀, F) — МП-автомат. Определим отношение (-, или просто

р

, когда Р подразумевается, следующим образом. Предположим, что 8(q, а, X) содержит (р, а). Тогда для всех цепочек w из £* и /3 из Г* полагаем (q, aw, Хр) (- (р, w, ар).

Этот переход отражает идею того, что, прочитывая на входе символ а, который мо­жет быть е, и заменяя ЛГ на вершине магазина цепочкой а, можно перейти из состояния q в состояние р. Заметим, что оставшаяся часть входа (vv) и содержимое магазина под его вершиной (р) не влияют на действие МП-автомата; они просто сохраняются, возможно,

для того, чтобы влиять на события в дальнейшем.

• *

Используем также символ , или просто (-, когда МП-автомат Р подразумевается,

для представления нуля или нескольких переходов МП-автомата. Итак, имеем следую­щее индуктивное определение.

Базис. I \- I для любого МО /,

Индукция. I \- J, если существует некоторое МО К, удовлетворяющее условиям / h К и К |- J.

Таким образом, I \- J, если существует такая последовательность МО К,, К₂, …, К„, у ко­торой / = K_h J= K„,nKi |- Kj+i для всех /’= 1, 2, …, п — 1.

Пример 6.4. Рассмотрим работу МП-автомата из примера 6.2 со входом 1111. По­скольку q₀ — начальное состояние, a Z₀ — стартовый символ, то начальным МО будет (q₀,1111, Z₀). На этом входе МП-автомат имеет возможность несколько раз делать оши­бочные предположения. Вся последовательность МО, достижимых из начальной конфи­гурации, показана на рис. 6.3. Стрелки представляют отношение |-.

Из начального МО можно выбрать два перехода. Первый предполагает, что сере­дина не достигнута и ведет к МО (q₀, 111, 1Z₀). В результате символ 1 перемещается в магазин.

Второй выбор основан на предположении, что достигнута середина входа. Без прочи- тывания очередного символа МП-автомат переходит в состояние q_h что приводит к МО (qi, 1111,Z₀). Поскольку МП-автомат может допустить вход, если он находится в со­стоянии qi и обозревает Z₀ на вершине магазина, он переходит к МО (q₂, 1111, Z₀). Это МО не является в точности допускающим, так как вход не дочитан до конца. Если бы входом вместо 1111 было £, то та же самая последовательность переходов привела к МО (qo, £, Z₀), показывающему, что г допущено.

МП-автомат может также предположить, что он увидел середину после чтения пер­вой 1, т.е. находясь в конфигурации (q₀, 111, 1Z₀). Это предположение также ведет к ошиб­ке, поскольку вход не может быть дочитан до конца. Правильное предположение, что сере­дина достигается после прочтения 11, дает последовательность МО (q₀, 1111 ,Z₀) |-

(q₀, 111, 1 Zo) h (Чо, 11, 1 iZ₀) h (ЧП, 1 Ш h (Чи 1, IZo) h (Чь e, Z₀) |- (g₂, e, Z₀). □

Соглашения по записи МП-автоматов

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

1. Символы входного алфавита представлены строчными буквами из начала алфави­та, например, а или Ь.
2. Состояния обычно представляются буквами р и q или другими, близкими к ним в алфавитном порядке.
3. Цепочки входных символов обозначаются строчными буквами из конца алфавита, например, w или г.
4. Магазинные символы представлены прописными буквами из конца алфавита, на­пример, X или
5. Цепочки магазинных символов обозначаются греческими буквами, например, а или /3.

(q,,E,llllZ₀) (qpE.UZj)                 (qpE.Ze)

‘ r

(q₂.^E—^zo)

Рис. 6.3. Конфигурации МП-автомата из примера 6.2 при входе 1111

Для дальнейших рассуждений о МП-автоматах понадобятся следующие три важных принципа.

1. Если последовательность конфигураций (вычисление) является допустимой (legal) для МП-автомата Р (с точки зрения его определения), то вычисление, образованное путем дописывания одной и той же цепочки к концам входных цепочек всех его конфигураций, также допустимо.
2. Если вычисление допустимо для МП-автомата Р, то вычисление, образованное до­писыванием одних и тех же магазинных символов внизу магазина в каждой конфи­гурации, также допустимо.
3. Если вычисление допустимо для МП-автомата Р, ив результате некоторый суффикс (tail) входной цепочки не прочитан, то вычисление, полученное путем удаления это­го суффикса из входных цепочек каждой конфигурации, также допустимо.

Интуитивно данные, которые никогда не читаются МП-автоматом, не влияют на его вы­числения. Формализуем приведенные пункты 1 и 2 в виде следующей теоремы.

Теорема 6.5. Если Р = (Q, Е, Г, <5, q₀, Z₀, F) — МП-автомат и (q, х, а) ^ (р, у, р), то

для любой цепочки w из Е* и у из Г* верно следующее утверждение. *

(q,xw, ay) (p,yw,/3y)

Заметим, что если у= е, то получается формальное утверждение приведенного выше принципа 1, а при w = е — принципа 2.

Доказательство. Доказательство проводится очень просто индукцией по числу ша­гов в последовательности МО, приводящих (q, xw, ay) к (р, yw, Ру). Каждый из переходов

в последовательности (q, х, а) \- (р,у, Р) обосновывается переходами Р без какого-либо

использования w и/или у. Следовательно, каждый переход обоснован и в случае, когда эти цепочки присутствуют на входе и в магазине. □

Заметим, что обращение этой теоремы неверно. Существуют действия, которые МП- автомат мог бы совершить с помощью выталкивания из стека, т.е. используя некоторые символы у и заменяя их в магазине, что невозможно без обработки у. Однако, как утвер­ждает принцип 3, мы можем удалить неиспользуемый вход, так как МП-автомат не мо­жет прочитать входные символы, а затем восстановить их на входе. Сформулируем принцип 3 следующим образом.

Нужны ли конфигурации конечных автоматов?

Можно было бы удивиться, почему понятие конфигурации не было введено для ко­нечных автоматов. Хотя конечный автомат не имеет магазина, в качестве МО для не­го можно было бы использовать пару (д, vv), где д — состояние, aw — остаток входа. Определить такие конфигурации можно, но их достижимость не дает никакой новой

Л

информации по сравнению с тем, что давало использование 8 . Иными словами, для любого конечного автомата можно показать, что 8 (q, w)=p тогда и только тогда, когда (q, wx) (- (р, х) для всех цепочек х. Тот факт, что х может быть чем угодно, не влияющим на поведение конечного автомата, является теоремой, аналогичной теоре­мам 6.5 и 6.6.

Теорема 6.6. Если Р = (Q, Z, Г, 8, q₀, Z₀, F) — МП-автомат и (q, xw, а) (р, yw, р), то верно также, что (q, х, а) (- (р, у, р). □

6.1.5. Упражнения к разделу 6.1

6.1.1. Предположим, что МП-автомат P = ({q, р], {0, 1}, (Z₀,X), S, q, Z„, {р}) имеет следующую функцию переходов.

1. 8(q,0,Z₀)={(q,XZ₀)}. 6.1. ОПРЕДЕЛЕНИЕ АВТОМАТОВ С МАГАЗИННОЙ ПАМЯТЬЮ 241

2.	S(q, 0,Х) =	{(Я, XX))
3.	S(q, 1,Х) =	{(Я,Х)).
4.	5(q,e,X) =
5.	5(р,е,Х) =
6.	S(p, \,Х) =	{{р,ХХ)}
7.	5(р, 1 ,Z0) =

Приведите все конфигурации, достижимые из начального МО (q, w, Z₀), если входным словом w является:

а)   01;

б)   0011; в) 010.

6.2. Языки МП-автоллатов

Мы предполагали, что МП-автомат допускает свой вход, прочитывая его и достигая заключительного состояния. Такой подход называется «допуск по заключительному со­стоянию». Существует другой способ определения языка МП-автомата, имеющий важ­ные приложения. Для любого МП-автомата мы можем определить язык, «допускаемый по пустому магазину», т.е. множество цепочек, приводящих МП-автомат в начальной конфигурации к опустошению магазина.

Эти два метода эквивалентны в том смысле, что для языка L найдется МП-автомат, допускающий его по заключительному состоянию тогда и только тогда, когда для L най­дется МП-автомат, допускающий его по пустому магазину. Однако для конкретных МП- автоматов языки, допускаемые по заключительному состоянию и по пустому магазину, обычно различны. В этом разделе показывается, как преобразовать МП-автомат, допус­кающий L по заключительному состоянию, в другой МП-автомат, который допускает L по пустому магазину, и наоборот.

6.2.1. Допустимость по заключительному состоянию

Пусть Р = (Q, Г, 8, q₀, Z₀, F) — МП-автомат. Тогда L(P), языком, допускаемым Р по заключительному состоянию, является

{w | (q₀, w, Z₀) ^ (q, £, a)}

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

Пример 6.7. Мы утверждали, что МП-автомат из примера 6.2 допускает язык L_mtn со­стоящий из цепочек вида ww^R в алфавите {0, 1}. Выясним, почему это утверждение верно. Оно имеет вид «тогда и только тогда, когда»: МП-автомат Р из примера 6.2 допускает це­почку х по заключительному состоянию тогда и только тогда, когда х имеет вид ww^R.

(Достаточность) Эта часть проста; нужно показать лишь допускающее вычисление Р. Если х = ww^R, то заметим, что справедливы следующие соотношения.

(q₀, ww^R, Z₀) \-(q₀, w^R, w^RZ₀) |- (q_h w^R, w^RZ₀) \-(q_t, £, Z₀) |- (q₂, £, Z₀) Таким образом, МП-автомат имеет возможность прочитать цепочку w на входе и запи­сать ее символы в свой магазин в обратном порядке. Затем он спонтанно переходит в со­стояние qi и проверяет совпадение w^R на входе с такой же цепочкой в магазине, и нако­нец, спонтанно переходит в состояние q₂.

(Необходимость) Эта часть труднее. Во-первых, заметим, что единственный путь достижения состояния q₂ состоит в том, чтобы находиться в состоянии q_t и иметь Z₀ на вершине магазина. Кроме того, любое допускающее вычисление Р начинается в состоя­нии q₀, совершает один переход в и никогда не возвращается в q₀. Таким образом, дос­таточно найти условия, налагаемые на х, для которых (q₀, х, Z₀) |- (q_h е, Z₀); именно та­кие цепочки и допускает Р по заключительному состоянию. Покажем индукцией по |х| следующее несколько более общее утверждение.

• Если (q₀, х, a) j- (q,, е, а), то х имеет вид ww^R.

Базис. Если х = е, то х имеет вид ww^R, с w = е. Таким образом, заключение верно, и утверждение истинно. Отметим, что нам не обязательно доказывать истинность гипотезы

(qo, £, а) \- (q_h е, а), хотя она и верна.

Индукция. Пусть х = а₁а₂…а„ для некоторого п > 0. Существуют следующие два пе­рехода, которые Р может совершить из МО (q₀, х, а).

1. (q₀, х, а) |- (q_t,x, а). Теперь Р может только выталкивать из магазина, находясь в состоянии q_t. Р должен вытолкнуть символ из магазина с чтением каждого входного

символа, и |х| > 0. Таким образом, если (q_h х, а) |- (q_h £, Д), то цепочка /? короче, чем а, и не может ей равняться.

2. (qo, а,а₂. ,.а„, а) |- (q_B, а₂…а„, а/а). Теперь последовательность переходов может закон­читься в (q_h £, а), только если последний переход является следующим выталкиванием.

(q,, а„, а,а) \- (q,, е, а) В этом случае должно выполняться а, = а„. Нам также известно, что

(Яо, а₂…а„, а,а) |- (q_h а„, а,а)

По теореме 6.6 символ а„ можно удалить из конца входа, поскольку он не использу­ется. Тогда

(q₀, а₂…а„.,, а,а) |- (q_h £, а,а) Поскольку вход у этой последовательности короче, чем п, можно применить индук­тивное предположение и заключить, что а₂…а_п., имеет вид »^,R для некоторого у. Поскольку х = а/уу^яа„, и нам известно, что a_t = а„, делаем вывод, что х имеет вид mv^R; в частности w = а _}у.

Приведенные рассуждения составляют сердцевину доказательства того, что х допус­кается только тогда, когда равен ww^R для некоторого w. Таким образом, необходимость доказана. Вместе с достаточностью, доказанной ранее, она гласит, что Р допускает в точности цепочки из L_mvr. □

• Допустимость по пустому магазину

Для каждого МП-автомата P = (Q, 2, Г, 5, q₀, Z₀, F) определим

N(P) = {w I (qo, w, Z₀) I- (q, e, e)},

где q— произвольное состояние. Таким образом, N(P) представляет собой множество входов w, которые Р может прочитать, одновременно опустошив свой магазин.^[2]

Пример 6.8. МП-автомат Р из примера 6.2 никогда не опустошает свой магазин, по­этому N(P) = 0. Однако небольшое изменение позволит автомату Р допускать L_mvr как по пустому магазину, так и по заключительному состоянию. Вместо перехода 5(q_h е, Z₀) = {(q₂,Z₀)} используем 5(q_h e,Z₀) = {(q₂, £)}■ Теперь P выталкивает последний символ из магазина, когда допускает, поэтому L(P) = N(P) = L_mir. □

Поскольку множество допускающих состояний не имеет значения, иногда в случаях, когда нас будет интересовать допуск только по пустому магазину, будем записывать МП-автомат в виде шестерки (Q, Z, Г, 8, q₀, Z₀), опуская седьмой компонент.

• От пустого магазина к заключительному состоянию

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

Теорема 6.9. Если L = N(P_n) для некоторого МП-автомата P_N = (Q, Е, Г, S_N, q₀, Z₀), то существует такой МП-автомат P_F, у которого L = L(P,.).

Доказательство. Идея доказательства представлена на рис. 6.4. Используется новый символ Х₀, который не должен быть элементом Г; Х₀ является как стартовым символом автомата P_F, так и маркером дна магазина, позволяющим узнать, когда P_N опустошает магазин. Таким образом, если Р,.- обозревает^ на вершине магазина, то он знает, что P_N опустошает свой магазин на этом же входе.

е,Х₀/е

Рис. 6.4. Р|. имитирует PN и допускает, если PN опустошает свой магазин

Нам нужно также новое начальное состояние р₀, единственной функцией которого является затолкнуть Z₀, стартовый символ автомата Р,у, на вершину магазина и перейти в состояние q₀, начальное для P_N. Далее P_F имитирует P_N до тех пор, пока магазин P_N не станет пустым, что P_F определяет по символу Х₀ на вершине своего магазина. И наконец, нужно еще одно новое состояние pf, заключительное в автомате Р/.; он переходит в как только обнаруживает, что P_N опустошает свой магазин. Описание P_F имеет следующий вид.

Рр= (в U {ро, Pf}, 2, Г U {Х₀}, S_F, ро, Хо, {_Pf\) Функция 3/. определяется таким образом.

1. S/.ipo, е,Х₀) = {(qo, ZoXo)}. В своем начальном состоянии Рр спонтанно переходит в начальное состояние автомата Рц, заталкивая его стартовый символ Z„ в магазин.
2. Для всех состояний q из Q, входов а из Е (или а = ё) и магазинных символов У из Г, 6/.{q, а, У) содержит все пары из 8>,(q, а, У).
3. В дополнение к правилу (2), 5/.{q, е, Х₀) содержит (p_fi е) для каждого состояния q из Докажем, что vv G ЦРу) тогда и только тогда, когда w g N(P_n).

(Достаточность) Нам дано, что (q₀, vv, Z„) |- (q, е, е) для некоторого состояния q. По

F,-

теореме 6.5 можно добавить Х₀ на дно магазина и заключить, что (q₀, vv, ZoXo) (- (q, е, Х₀). Поскольку по правилу 2 у P_F есть все переходы P_N, можно утверждать также, что (q₀, w, ZoXo) |- (q, e, X₀). Если эту последовательность переходов собрать вместе с

р»

начальным и заключительным переходами в соответствии с правилами 1 и 3, то получим следующее.

(ро, w,X₀) |- (q₀, w, ZoXo) |- (q, e,X₀) |- (p_f, e, e)                                 (6.1)

p_f                                          pf                               p_e

Таким образом, P_F допускает w по заключительному состоянию.

(Необходимость) Заметим, что дополнительные переходы по правилам 1 и 3 дают весьма ограниченные возможности для допускания w по заключительному состоянию. Правило 3 должно использоваться только на последнем шаге, и его можно использовать, если магазин Pf содержит лишь Х„. Но Х₀ не появляется нигде в магазине, кроме его дна. Правило 1 использу­ется только на первом шаге, и оно должно использоваться на первом шаге.

Таким образом, любое вычисление в автомате / /.. допускающее w, должно выглядеть как последовательность (6.1). Более того, середина вычисления (все переходы, кроме первого и последнего) должна также быть вычислением в P_N с Х₀ под магазином. Это обусловлено тем, что, за исключением первого и последнего шагов, P_F не может исполь­зовать переходы, которые не являются переходами P_N, и Х„ не может оказаться на вер­шине магазина (иначе вычисление заканчивалось бы на следующем шаге). Таким обра­зом, (q₀, w, Z₀) |- (q, £, е), и w G N(P_n). □ р_к

Пример 6.10. Построим МП-автомат, который обрабатывает последовательности слов if и else в С-программе, где i обозначает if, а е — else. Как показано в разде­ле 5.3.1, в любом префиксе программы количество else не может превышать числа if, поскольку в противном случае слову else нельзя сопоставить предшествующее ему if. Итак, магазинный символ Z используется для подсчета разницы между текущими коли­чествами просмотренных i и е. Этот простой МП-автомат с единственным состоянием представлен диаграммой переходов на рис. 6.5.

е, Z/e i,Z/ZZ Рис. 6.5. МП-автомат, допускающий ошибки if/else по пустому магазину

Увидев /, автомат заталкивает Z, а е — выталкивает. Поскольку он начинает с одним Z в магазине, в действительности он следует правилу, что если в магазине Z», то симво­лов I прочитано на п — 1 больше, чем е. В частности, если магазин пуст, то символов е прочитано на один больше, чем /, и входная последовательность недопустима в С-прог-
рамме. Именно такие цепочки наш МП-автомат P_N допускает по пустому магазину. Его формальное определение имеет следующий вид.

Лг=({<7}, {‘,*}, {Z},8_N,q,Z) Функция <5_Л: задается таким образом.

1. Spjiq, i, Z) = {(<7, ZZ)}. По этому правилу заталкивается Z при i на входе.
2. dpiiq, е, Z) = {(q, £)}. Zвыталкивается при входе е.

e,Zle i.ZIZZ

Рис. 6.6. Конструкция МП-автомата, допускающего по заключительному состоянию и построенного на основе автомата (см. рис. 6.5)

Теперь на основе P_N построим МП-автомат P_F, допускающий этот же язык по заклю­чительному состоянию; его диаграмма переходов показана на рис. 6.6.^[3] Вводим новые начальное и заключительное состояния р и г, а также используем Х₀ в качестве маркера дна магазина. Формально автомат/V определяется следующим образом.

Pf= ({Л Я, г}, {/, е}, {Z, Х₀}, S_F, q, Z) Функция 8_f задается таким образом.

1. 8/.(р, е,Х₀) = {(q, ZX₀)}. По этому правилу P_F начинает имитировать P_N с маркером дна магазина.
2. 8f(q, i,Z) = {(q, ZZ)}. Z заталкивается при входе i, как у P_N.
3. 8f(q, е, Z) = {(q, e)}. Z выталкивается при входе e, как у P_N.
4. 8f{q, e, X₀) = {(r, e)}. P_F допускает, когда имитируемый P_N опустошает свой магазин. □

6.2.4. От заключительного состояния к пустому магазину

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

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

Во избежание имитации случая, когда P_F случайно опустошает свой магазин без до­пуска, P_N должен также использовать маркер Х₀ на дне магазина. Маркер является его стартовым символом и аналогично конструкции теоремы 6.9 P_N должен начинать работу в новом состоянии ро, единственная функция которого — затолкнуть стартовый символ автомата P_F в магазин и перейти в начальное состояние P_F. В сжатом виде конструкция представлена на рис. 6.7, а ее формальное описание приводится в следующей теореме.

Рис. 6.7. PN имитирует PF и опустошает свой магазин тогда и только тогда, когда PF достигает заключительного состояния

е. любой/Е Е, любой/Ё

Теорема 6.11. Пусть L = L(P_F) для некоторого МП-автомата P_F = (Q, Е, Г, S_F, q₀, Z₀, F). Тогда существует такой МП-автомат P_N, у которого L = N(P_n). Доказательство. Конструкция соответствует рис. 6.7. Пусть

Pn=(Q и {ро, р), 2, Г и {Хо}, 8_n, Ро, Х₀),

где 8_N определена следующим образом.

1. е,Х₀) = {(с/о, ZoXo)}. Работа начинается с заталкивания стартового символа ав­томата P_F в магазин и перехода в его начальное состояние.
2. Для всех состояний q из Q, входов а из Е или а = е и магазинных символов Y из Г 8_s(q, a, Y) содержит все пары из 8,.{q, a, Y), т.е. P_N имитирует P_F.
3. Для всех допускающих состояний q из F и магазинных символов Y из Г U {%»}

8^(q, е, Y) содержит (р, е). По этому правилу, как только P_F допускает, P_N может на­чать опустошение магазина без чтения входных символов.

4. Для всех магазинных символов Y из Г U {^о}, 8ц(р, е, Y) = {(р, £)}. Попав в состояние

р (только в случае, когда P_F допускает), P_N выталкивает символы из магазина до его опустошения. Входные символы при этом не читаются.

Теперь нужно доказать, что vv е N(P_n) тогда и только тогда, когда w е L(P_h-). Идеи аналогичны теореме 6.9. Достаточность представляет собой непосредственную имита­цию, а необходимость требует проверки ограниченного числа действий, которые может совершить МП-автомат P_N.

(Достаточность) Пусть (q₀, vv, Z₀) (- (q, £, а) для некоторого допускающего состояния

р,

q и цепочки а в магазине. Вспомним, что каждый переход P_F есть и у Ру, и что теорема 6.5

*

разрешает нам держать Х₀ в магазине под символами из Г. Тогда (q,_h vv, ZoXo) h (я, ccX₀).

P.V

Следовательно, P_N может совершить следующие действия.

(ро, W, Х₀) I- (qo, w, ZoXo) |- (q, e, aX₀) (p, e, e)

p_s

Первый переход соответствует правилу 1 построения P_N, а последняя последователь­ность переходов — правилам 3 и 4. Таким образом, P_N допускает w по пустому магазину.

(Необходимость) Единственный путь, по которому P_N может опустошить свой ма­газин, состоит в достижении состояния р, так как Х₀ находится в магазине и является символом, для которого у P_F переходы не определены. P_N может достичь состояния р только тогда, когда P_F приходит в допускающее состояние. Первым переходом авто­мата P_N может быть только переход, заданный правилом 1. Таким образом, каждое до­пускающее вычисление Рц выглядит следующим образом (q — допускающее состоя­ние автомата /V).

(ро, w, Х₀) b (Яо, w, ZoXo) h (q, е, аХ₀) |- (р, е, е)

Р»                         Р»                      Рх

Кроме того, между МО (q₀, w, ZoXo) и (q, е, аХ₀) все переходы являются переходами автомата P_f. В частности, Х„ никогда не появляется на вершине магазина до достижения МО (q, е, <xYo).^[4] Таким образом, приходим к выводу, что у P_F есть такое же вычисление,

но безЛ’о в магазине, т.е. (q₀, vv, Z₀) (q, е, а). Итак, P_F допускает w по заключительному

Pf

состоянию, т.е. w е ЦР/ )- П

6.2.5. Упражнения к разделу 6.2

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

а)  (*) {0″1^п | л> 1};

б)  множество всех цепочек из 0 и 1, в префиксах которых количество символов 1 не больше количества символов 0;

в)   множество всех цепочек из 0 и 1 с одинаковыми количествами символов 0 и 1.

• (!) Постройте МП-автоматы, допускающие следующие языки:

а)  (*) {db^]c^v | i=j или j = к}. Заметим, что этот язык отличается от языка из уп­ражнения 5.1.1, б;

б)  множество всех цепочек из 0 и 1, у которых количество символов 0 вдвое больше количества символов 1.

• (!!) Постройте МП-автоматы, допускающие следующие языки:

а)  {d&c^k | или j * к];

б)  множество всех цепочек из символов а и Ь, которые не имеют вида ww, т.е. не являются повторениями никакой цепочки.

• Пусть Р — МП-автомат, допускающий по пустому магазину язык L = N(P), и пусть eg Опишите, как изменить Р, чтобы он допускал L U {£} по пустому магазину.
• МП-автомат Р = ({q₀, q_h q₂, q₃,f}, {a, b}, {Z₀, A, B}, 5, q₀, Z₀, {/}) имеет следую­щее определение

8(q₀, a, Z₀) = {q,, AAZ„) 8{q₀, b, Z„) = (q₂, BZ₀) 8(q₀, e, Z₀) = (/,£) 8{q_h a, A) = (q_h AAA) 8{q_h b, A) = {q_h s) 8(q_h £, Z₀) = {q₀, Z₀) S(q₂, a, B) = (q₃, £)   8(q₂, b, B) = (q₂, BB) S(q₂, £, Z₀) = (q_lh Z₀)

8(q₃, £, B) = (q₂, £)                 8(q₃, £, Z₀) = (q_h AZ₀)

Фигурные скобки опущены, поскольку каждое из указанных множеств имеет только один выбор перехода.

а)  (*) приведите трассу выполнения (последовательность МО), по которой вид­но, что bab е L(P);

б)  приведите трассу выполнения, показывающую, что abb е ЦР);

в)   укажите содержимое магазина после того, как Р прочитал Ь¹ а на входе;

г)   (!) дайте неформальное описание L(P).

• Рассмотрим МП-автомат Р из упражнения 6.1.1:

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

N(P,) = L(P)-,

б)  постройте МП-автомат Р₂ такой, что ЦР₂) = N(P), т.е. Р₂ допускает по за­ключительному состоянию то, что Р допускает по пустому магазину.

• (!) Покажите; что если Р — МП-автомат, то существует МП-автомат Р₂, у кото­рого только два магазинных символа и L(P₂) = L(P). Указание. Рассмотрите дво­ичное представление магазинных символов Р.

6.2.8. (*!) МП-автомат называется ограниченным, если при любом переходе он может увеличивать высоту магазина не более, чем на один символ. Таким образом, ес­ли (р, у) содержится в функции переходов, то |у| < 2. Докажите, что если Р— МП-автомат, то существует ограниченный МП-автомат Р₃, для которого

Щ>з) = L(P).

6.3. Эквивалентность МП-автоматов и КС-грамматик

В этом разделе мы покажем, что МП-автоматы определяют КС-языки. План доказа­тельства изображен на рис. 6.8. Цель состоит в том, чтобы доказать равенство следую­щих классов языков.

1. Класс КС-языков, определяемых КС-грамматиками.
2. Класс языков, допускаемых МП-автоматами по заключительному состоянию.
3. Класс языков, допускаемых МП-автоматами по пустому магазину.

Мы уже показали, что классы 2 и 3 равны. После этого достаточно доказать, что сов­падают классы 1 и 2.

Рис. 6.8. Организация конструкций, показывающих эквивалентность трех способов определения КС-языков

6.3.1. От грамматик к МП-автоматам

По данной грамматике G строится МП-автомат, имитирующий ее левые порождения. Любую левовыводимую цепочку, которая не является терминальной, можно записать в виде хАа, где А — крайняя слева переменная, х — цепочка терминалов слева от А, а — цепочка терминалов и переменных справа. А а называется остатком (tail) этой левовы- водимой цепочки. У терминальной левовыводимой цепочки остатком является е.

Идея построения МП-автомата по грамматике состоит в том, чтобы МП-автомат ими­тировал последовательность левовыводимых цепочек, используемых в грамматике для порождения данной терминальной цепочки w. Остаток каждой цепочки А а появляется в магазине с переменной А на вершине. При этом х «представлен» прочитанными на входе символами, а суффикс цепочки w после х считается непрочитанным.

Предположим, что МП-автомат находится в конфигурации (q, у, А а), представляю­щей левовыводимую цепочку хА а. Он угадывает продукцию, используемую для расши­рения А, скажем, А —» Д. Переход автомата состоит в том, что А на вершине магазина за­меняется цепочкой Д, и достигается МО (q, у, Ра). Заметим, что у этого МП-автомата есть всего одно состояние, q.

Теперь (q, у, Ра) может не быть представлением следующей левовыводимой цепочки, поскольку Д может иметь терминальный префикс. В действительности, Д может вообще не иметь переменных, а у а может быть терминальный префикс. Все терминалы в начале цепочки Да нужно удалить до появления следующей переменной на вершине магазина. Эти терминалы сравниваются со следующими входными символами для того, чтобы убедиться, что наши предположения о левом порождении входной цепочки w правильны; в противном случае данная ветвь вычислений МП-автомата отбрасывается.

Если таким способом нам удается угадать левое порождение w, то в конце концов мы дойдем до левовыводимой цепочки vv. В этот момент все символы в магазине или рас­ширены (если это переменные), или совпали с входными (если это терминалы). Магазин пуст, и мы допускаем по пустому магазину.

Уточним приведенное неформальное описание. Пусть G=(V,T,Q,S)— КС- грамматика. Построим МП-автомат P = ({q), Т, V{J Т, 8, q,S), который допускает L(G) по пустому магазину. Функция переходов 8 определена таким образом:

1. 8(q, е, А) = {(q, Д) | А —> Д — продукция G} для каждой переменной А.
2. 8(q, а, а) = {(q, е)} для каждого терминала а.

Пример 6.12. Преобразуем грамматику выражений (см. рис. 5.2) в МП-автомат. На­помним эту грамматику.

I->a\b\Ia\Ib\IO\Il E-)I\E*E\E + E\ (Е) Множеством входных символов для МП-автомата является {а, Ь, 0, 1, (,),+, *}. Эти во­семь символов вместе с переменными / и Е образуют магазинный алфавит. Функция пе­реходов определена следующим образом:

а)   8(q, е,Г)= {(д, a), (q, b), (q, la), (q, lb), (q, 10), (q, /1)};

б)   8(q, e, E) = {(,q, I), (q, E + E), (q, E * E), (q, (£))};

в)   8(q, a, a) = {(q, e)}; 8(q, b, b) = {(q, e)}; 8(q, 0, 0) = {(q, e)}; 8(q, 1, 1) = {{q, e)};

8(q, (, () = {(q, £)}; 8(q, ), )) = {(q, e)}; 8(q, +, +) = {(q, e)}; 8(q, *, *) = {(q, e)}.

Заметим, что пункты (а) и (б) появились по правилу 1, а восемь переходов (в) — по пра­вилу 2. Других переходов у МП-автомата нет.

Теорема 6.13. Если МП-автомат Р построен по грамматике G в соответствии с опи­санной выше конструкцией, то N(P) = L(G).

Доказательство. Докажем, что vv е N(P) тогда и только тогда, когда vv е L(G).

(Достаточность) Пусть vv е L(G). Тогда w имеет следующее левое порождение.

S=Yi => 72 => ■■■ => y» = w

lm             lm               lm

Покажем индукцией по /’, что (q, и\ S) (q,y„ а,), где у, и а, представляют левовыводи­мую цепочку у. Точнее, пусть сц является остатком у, и у, = х,а,. Тогда у, — это такая це­почка, что ху, = w, т.е. то, что остается на входе после чтения х,.

*

Базис, у/ = S при / = 1. Таким образом, = £, и у/ = w. Поскольку (q, w, S) |- (q, w, S) через 0 переходов, базис доказан.

Индукция. Теперь рассмотрим вторую и последующие левовыводимые цепочки. Предположим, что

(q,w,S) \- (q,y„ а,) *

и докажем, что (q, w, S) \- (q,y_hi, <*;/)• Поскольку а, является остатком, он начинается переменной А. Кроме того, шаг порождения у, => у,_; включает замену переменной А од-

1т

ним из тел ее продукций, скажем, Д Правило 1 построения Р позволяет нам заменить А на вершине магазина цепочкой Д а правило 2 — сравнить затем любые терминалы на вершине магазина со следующими входными символами. В результате достигается МО (q,y,-i, <y., i), которое представляет следующую левовыводимую цепочку у,

Для завершения доказательства заметим, что а_п = £, так как остаток цепочки у, (а она

представляет собой w) пуст. Таким образом, (q, w, S) |- (q, е, ё), т.е. Р допускает w по пустому магазину.

(.Необходимость) Нам нужно доказать нечто более общее, а именно: если Р выполня­ет последовательность переходов, в результате которой переменная А удаляется из вер­шины магазина, причем магазин под ней не обрабатывается, то из А в грамматике G по­рождается любая цепочка, прочитанная на входе в этом процессе. Формально: * *

• если (q, х, А) |- (q, £, £), то А => jc.

Доказательство проведем индукцией по числу переходов, совершенных Р.

Базис. Один переход. Единственной возможностью является то, что А —» £ — про­дукция грамматики G, и эта продукция использована в правиле типа 1 МП-автоматом Р. В этом случае х = £, и А => £.

Индукция. Предположим, что Р совершает п переходов, где п > 1. Первый переход должен быть типа 1, где переменная А на вершине магазина заменяется одним из тел ее продукций. Причина в том, что правило типа 2 может быть использовано, когда на вер­шине магазина находится терминал. Пусть использована продукция А —> Y,Y₂…Y_k, где каждый Y, есть либо терминал, либо переменная.

В процессе следующих п — 1 переходов Р должен прочитать х на входе и вытолкнуть Y;, …, Y_k из магазина по очереди. Цепочку х можно разбить на подцепочки х,х2…х_к>

где Xi— порция входа, прочитанная до выталкивания Y, из магазина, т.е. когда длина магазина впервые уменьшается до к-\. Тогда х₂ является следующей порцией входа, читаемой до выталкивания Y₂, и т.д.

На рис. 6.9 представлены разбиение входа х и соответствующая обработка магазина. Предполагается, что [5 имеет вид ВаС, поэтому л: разбивается на три части х,х₂х₃, где х₂ = а. Заметим, что вообще, если У, — терминал, то х, также должен быть терминалом.

Рис. 6.9. МП-автомат А прочитывает х и удаляет ВаС из своего магазина * Формально мы можем заключить, что (q, xix,,h..xk, Y,) \- (q, х, ,….гд., е) для всех i = 1, 2, …, к. Кроме того, длина ни одной из этих последовательностей переходов не превы­шает п- 1, поэтому применимо предположение индукции в случае, если Yt— перемен­ная. Таким образом, можно заключить, что Yt => jc,-. Если Y, — терминал, то должен совершаться только один переход, в котором прове­ряется совпадение х, и У,. Опять-таки, можно сделать вывод, что Yt => х,; на этот раз по­рождение пустое. Теперь у нас есть порождение

А => Y,Y₂…Y_k => x,Y₂…Y_k => … => х,х₂…х_к. *

Таким образом, А => х.

Для завершения доказательства положим А = S и x = w. Поскольку нам дано, что

w £ ЩР), то (q, vv, j- (q, £, £)■ По доказанному индукцией имеем S => w, т.е. w е L(G). □

6.3.2. От МП-автоматов к грамматикам

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

Рис. 6.10. МП-автомат совершает последовательность переходов, в результате которых символы по одному удаляются из магазина

На рис. 6.10 показано, как последовательность символов Y_h Y₂, …, Y_k удаляется из магазина. До удаления Y_l прочитывается вход х,. Подчеркнем, что это «удаление» явля­ется окончательным результатом, возможно, многих переходов. Например, первый пере­ход может изменить У, на некоторый другой символ Z, следующий — изменить Z на UV, дальнейшие переходы — вытолкнуть U, а затем V. Окончательный результат заключает­ся в том, что Yi изменен на ничто, т.е. вытолкнут, и все прочитанные к этому моменту входные символы образуют X/.

На рис. 6.10 показано также окончательное изменение состояния. Предполагается, что МП-автомат начинает работу в состоянии р₀ с У) на вершине магазина. После всех переходов, результат которых состоит в удалении УМП-автомат находится в состоянии Pi. Затем он достигает окончательного удаления У₂, прочитывая при этом х₂ и приходя, возможно, за много переходов, в состояние р₂. Вычисление продолжается до тех пор, по­ка каждый из магазинных символов не будет удален.

Наша конструкция эквивалентной грамматики использует переменные, каждая из ко­торых представляет «событие», состоящее в следующем.

1. Окончательное удаление некоторого символа X из магазина.
2. Изменение состояния от некоторого р (вначале) до q, когда X окончательно заменя­ется £ в магазине.

Такую переменную обозначим составным символом [pXq], Заметим, что эта последова­тельность букв является описанием одной переменной, а не пятью символами граммати­ки. Формальное построение дается следующей теоремой.

Теорема 6.14. Пусть Р = (Q, 2, Г, <5, q₀, Z₀)— МП-автомат. Тогда существует КС- грамматика G, для которой L(G) = N(P).

Доказательство. Построим G = (V, R, S), где Vсостоит из следующих переменных.

1. Специальный стартовый символ
2. Все символы вида [pXq], где р и q — состояния из Q, аХ— магазинный символ из Г. Грамматика G имеет следующие продукции:

а)  продукции S —» \q_nZ_np] для всех состояний р. Интуитивно символ вида [qoZop] предназначен для порождения всех тех цепочек w, которые приводят Р к выталкиванию Z₀ из магазина в процессе перехода из состояния q₀ в со­стояние р. Таким образом, (q, w, Z₀) (q, £, £). Эти продукции гласят, что стартовый символ S порождает все цепочки w, приводящие Р к опустошению магазина после старта в начальной конфигурации;

б)  пусть S(q, а, X) содержит пару (г, К/ К₂… ¥>,), где а есть либо символ из либо £, а к — некоторое неотрицательное число; при к = 0 пара имеет вид (г, е). Тогда для всех списков состояний г,, г₂, …, г и в грамматике G есть продукция

[qXr_k] ^ a[rY,r,][г,Y₂r₂)…[r_{k l}Y_kr_k].

Она гласит, что один из путей выталкивания X и перехода из состояния q в состояние г_к заключается в том, чтобы прочитать а (оно может быть равно £), затем использовать некоторый вход для выталкивания Y_: из магазина с пере­ходом из состояния г в состояние r_h далее прочитать некоторый вход, вы­толкнуть У₂ и перейти из г\ в г₂, и т.д.

Докажем корректность неформальной интерпретации переменных вида [qXp]:

* [ЧХр\ => w тогда и только тогда, когда {q, w,X) |- (р, £, £).

* *

(Достаточность) Пусть (q, w,X) |~ (р» ^£)- Докажем, что [qXp] => w, используя ин­дукцию по числу переходов МП-автомата.

Базис. Один шаг. Пара (р, е) должна быть в S(q, w, X), и w есть либо одиночный символ, либо е. Из построения G следует, что [qXp] —> w является продукцией, поэто­му [qXp] => w.

*

Индукция. Предположим, что последовательность (q, w,X) \- (р, е, е) состоит из я переходов, и « > 1. Первый переход должен иметь вид

(q, vv, JQ К                                    (р, е, е),

где w = «Л^—для некоторого а, которое является либо символом из 2, либо е. Отсюда следу­ет, что пара (r₀, Y/Y₂…Y_k) должна быть в S(q, а,Х). Кроме того, по построению G сущест­вует продукция [qXr_k] a[r_f)Y_tr,}\r_tГ,/-,]…[r_k ,Y_kr_k], у которой r_k= р и п, г₂, …,г_к , — не­которые состояния из Q.

На рис. 6.10 показано, что символы Y_h Y₂, …, Y_k удаляются из магазина по очереди, и для /= 1, 2, …, к — 1 можно выбрать состояние р„ в котором находится МП-автомат при удалении Y,. Пусть Х- wi\v₂…w_k, где w,— входная цепочка, которая прочитывается до

удаления Y, из магазина. Тогда (/•,_/, w„ У,) |- (/•„ е, е).

Поскольку ни одна из указанных последовательностей переходов не содержит более, чем п переходов, к ним можно применить предположение индукции. Приходим к выво­ду, что     => и’,. Соберем эти порождения вместе.

[qXr_k] => afr^V;]^,^]—^ => *

avv/[> i 2] ■ ■ ■ Vк /УкГ_к] =>

awiw2-..w_k = w Здесь г* =/;.

(Необходимость) Доказательство проводится индукцией по числу шагов в порождении.

Базис. Один шаг. Тогда [qXp] —» w должно быть продукцией. Единственная возмож­ность для существования этой продукции — если в Р есть переход, в котором X вытал­кивается, а состояние q меняется на р. Таким образом, пара (р, е) должна быть в S(q, а, X), и а = w. Но тогда (q, w, X) |- (р, £, £).

Индукция. Предположим, что [qXp] => w за п шагов, где п > 1. Рассмотрим подроб­но первую выводимую цепочку, которая должна выглядеть следующим образом.

*

[qXr_t] => a[r₀Y,r,][r,Y₂r₂]…[r_k_,Y^_k] => w Здесь г_к = р. Эта продукция должна быть в грамматике, так как (r₀, YiY₂…Y_k) есть в 8(q, а, X).

Цепочку w можно разбить на w = awiw₂… w_k так, что [г, , К,/-,] => w, для всех г = 1,2,…, А: — 1. По предположению индукции для всех этих / верно следующее утверждение.

(‘•/-/, w„ У,) Ь (г,, е, £)

Используя теорему 6.5 для того, чтобы поместить нужные цепочки вокруг Wj на входе и под Yj в магазине, получим

(n-_hWiW^,…w_k, Y,Yj,,…Y_k) f- (r„w,₄…w_k, Y,.,…Y_k).

Соберем все эти последовательности вместе и получим следующее порождение.

*

(q,2L-w,w₂…w_k,X) (r₀,w,w₂…w_k, Y,Y₂…Y_k) \-

* * *

(r_hw₂w₃…w_k, Y₂Y₃…Y_k) \- (r₂,w₃…w_k, Y₃…Y_k) … (r_k, £, £) Поскольку r_k = p, мы доказали, что (q, w, X) (p, e, e).

Завершим доказательство. S => w тогда и только тогда, когда [q₀Zp₀] => w для неко­торого р в соответствии с построенными правилами для стартового символа S. Выше уже * *

доказано, что [qoZpo] => w тогда и только тогда, когда (q, w, Z₀) (р, £, £), т.е. когда Р допускает w по пустому магазину. Таким образом, L(G) — N(P). □

Пример 6.15. Преобразуем в грамматику МП-автомат P_N= {/, е}, {Z}, 8_N, q, Z) из примера 6.10. Напомним, что P_N допускает все цепочки, которые нарушают правило, что каждое е (else) должно соответствовать некоторому предшествующему i (if). Так как P_N имеет только одно состояние и один магазинный символ, грамматика строится про­сто. В ней есть лишь следующие две переменные:

а)   S— стартовый символ, который есть в каждой грамматике, построенной ме­тодом теоремы 6.14;

б)   IqZq] — единственная тройка, которую можно собрать из состояний и мага­зинных символов автомата Рц.

Грамматика G имеет следующие продукции.

1. Единственной продукцией для S является S —¥ [qZq]. Но если бы у МП-автомата бы­ло п состояний, то было бы и п продукций такого вида, поскольку последним может быть любое из п состояний. Первое состояние должно быть начальным, а магазин­ный символ — стартовым, как в нашей продукции выше.
2. Из того факта, что 8_s(q, i, Z) содержит (q, ZZ), получаем продукцию

[qZq] —> i[qZq][qZq], В этом простом примере есть только одна такая продукция. Но если бы у автомата было п состояний, то одно такое правило порождало бы п про­дукций, поскольку как промежуточным состоянием в теле, так и последним состоя­нием в голове и теле могли быть любые два состояния. Таким образом, если бы г и р

были двумя произвольными состояниями, то создавалась бы продукция [qZp] i[qZr][rZp],

3. Из того, что S^q, е, Z) содержит (q. £), получаем продукцию [qZq] —> е. Заметим, что в этом случае список магазинных символов, которыми заменяется Z, пуст, поэтому единст­венным символом в теле является входной символ, приводящий к этому переходу. Можно для удобства заменить тройку [qZq] каким-либо простым символом, например А. В таком случае грамматика состоит из следующих продукций.

S-M

АiA А \е

В действительности можно заметить, что S и А порождают одни и те же цепочки, поэто­му их можно обозначить одинаково и записать грамматику в окончательном виде.

G = ({£}, {/, е}, {S->iSS\e},S)

□

6.3.3. Упражнения к разделу 6.3

• (*) Преобразуйте грамматику

| А

А —» 1А0 | S | е

в МП-автомат, допускающий тот же язык по пустому магазину.

• Преобразуйте грамматику

S-» аАА A->aS\bS\ а

в МП-автомат, допускающий тот же язык по пустому магазину.

• (*) Преобразуйте МП-автомат Р = ({/?, q], {0, 1}, {X, Z₀}, д, q, Z₀) в КС-грамма- тику, где д задана следующим образом.
  1. S(q,l,Z₀) = {(q,XZ₀)}.
  2. S(q,l,X)={(q,XX)}.
  4. S(q,£,X)={(q,e)).
  5. Sip, l,X) = {(p,e)}.
  6. Sip,0,Z₀) = {(q,Z₀)}.
• Преобразуйте МП-автомат из упражнения 6.1.1 в КС-грамматику.
• Ниже приведены КС-языки. Постройте для каждого из них МП-автомат, допус­кающий этот язык по пустому магазину. При желании можно сначала построить КС-грамматику для этого языка, а затем преобразовать ее в МП-автомат.

а)   {aⁿ6^mc^2(n+m)|«>0,w>0};

б)   {а’Ь?с^к | i = 2j или j = 2k};

в)   {О» 1^ш | и < m < 2/г}.

• (*!) Докажите, что если Р— МП-автомат, то существует МП-автомат Р/ с од­ним состоянием, для которого N(P,) = N(P).
• (!) Пусть у нас есть МП-автомат с 5 состояниями, t магазинными символами, в правилах которого длина цепочки, замещающей символ в магазине, не пре­вышает и. Дайте как можно более точную верхнюю оценку числа переменных КС-грамматики, которая строится по этому МП-автомату с помощью метода из раздела 6.3.2.

6.4. Детерминированные автоматы с магазинной памятью

Хотя МП-автоматы по определению недетерминированы, их детерминированный случай чрезвычайно важен. В частности, синтаксические анализаторы в целом ведут себя как детерминированные МП-автоматы, поэтому класс языков, допускаемых этими авто­матами, углубляет понимание конструкций, пригодных для языков программирования. В этом разделе определяются детерминированные МП-автоматы и частично исследуются работы, которые им под силу и на которые они не способны.

6.4.1. Определение детерминированного МП-автомата

Интуитивно МП-автомат является детерминированным, если в любой ситуации у него нет возможности выборов перехода. Эти выборы имеют два вида. Если S(q, а, ЛС) содер­жит более одной пары, то МП-автомат безусловно не является детерминированным, по­скольку можно выбирать из этих двух пар. Однако если 8{q, а,Х) всегда одноэлементно, все равно остается возможность выбора между чтением входного символа и совершени­ем £-перехода. Таким образом, МП-автомат Р = (О, Г, <5, q₀, Z_(h F) определяется как детерминированный (ДМП-автомат), если выполнены следующие условия.

1. S(q, а, X) имеет не более одного элемента для каждого q из Q, а из X или а = £ иХт Г.
2. Если 8{q, а, X) непусто для некоторого а из то 8{q, £, X) должно быть пустым. Пример 6.16. Оказывается, КС-язык L,,_1IT из примера 6.2 не имеет ДМП-автомата.

Однако путем помещения «центрального маркера» с в середину слов получается язык Lwcwr = {vt’cvv^R I we (0 + 1)*}, распознаваемый некоторым ДМП-автоматом.

Стратегией этого ДМП-автомата является заталкивание символов 0 и 1 в магазин до появления на входе маркера с. Затем автомат переходит в другое состояние, в котором сравнивает входные и магазинные символы и выталкивает магазинные в случае их сов­падения. Находя несовпадение, он останавливается без допускания («умирает»); его вход не может иметь вид wcw^K. Если путем удаления магазинных символов он достигает стар­тового символа, отмечающего дно магазина, то он допускает свой вход.

По своей идее этот автомат очень похож на МП-автомат, изображенный на рис. 6.2. Однако тот МП-автомат был недетерминированным, поскольку в состоянии q₀ всегда имел возможность выбора между заталкиванием очередного входного символа в магазин и переходом в состояние q_: без чтения входа, т.е. он должен был угадывать, достигнута ли середина. ДМП-автомат для L,_miT изображен в виде диаграммы переходов на рис. 6.11.

• z₀/oz₀
• z_e/iz_e 0,0/00 0,1/01

1,0/10          0,0/е

1,1/11         1,1/Е

Начало y^N                         ‘/'»N

—————————————————————-

с, z₀/z₀               е, Z₀/Z₀ ‘

с, 0/0

с, 1/1

Рис. 6.11. ДМП-автомат, допускающий

Очевидно, этот МП-автомат детерминирован. У него никогда нет выбора перехода в одном и том же состоянии и при использовании одних и тех же входных и магазинных символов. Что же касается выбора между использованием входного символа или е, то единственным е-переходом, который он совершает, является переход из qi в q₇ с Z₀ на вершине магазина. Однако в состоянии q, с Z₀ на вершине других переходов нет. □

6.4.2. Регулярные языки и детерминированные МП-автоматы

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

Теорема 6.17. Если L — регулярный язык, то L = L(P) для некоторого ДМП-автомата Р.

Доказательство. По существу, ДМП-автомат может имитировать детерминирован­ный конечный автомат. МП-автомат содержит некоторый символ Z₀ в магазине, так как он должен иметь магазин, но в действительности он игнорирует магазин, используя только состояние. Формально, пусть А = (Q, S_A, q₀, F) — конечный автомат. Построим /•= (g, Z, {Z_rt}, S_P, q₀, Z₀, F), определив 8_P(q, a, Z₀) = {(p, Z₀)} для всех состояний p и q из Q, при которых S_A(q, а) = p.

Мы утверждаем, что (q₀, w, Z_a) (- (р, £, Z₀) тогда и только тогда, когда д (q₀, vv) = р, т.е. Р имитирует А, используя его состояние. Доказательства в обе стороны просты и проводятся индукцией по |w|, поэтому оставляются для завершения читателю. Поскольку как А, так и Р допускают, достигнув какого-либо состояния из F, приходим к выводу, что их языки равны. □       ¹

Если мы хотим, чтобы ДМП-автомат допускал по пустому магазину, то обнаружива­ем, что возможности по распознаванию языков существенно ограничены. Говорят, что язык L имеет префиксное свойство, или свойство префиксности, если в L нет двух раз­личных цепочек х и у, где х является префиксом у.

Пример 6.18. Язык L,_m„_r из примера 6.16 имеет префиксное свойство, т.е. в нем не может быть двух разных цепочек wc\v^K и xcx^R, одна из которых является префиксом дру­гой. Чтобы убедиться в этом, предположим, что wcw^R — префикс jccc^r, и и’ Ф х. Тогда w должна быть короче, чем х. Следовательно, с в w приходится на позицию, в которой л: имеет 0 или 1, а это противоречит предположению, что wcw^R — префикс xcx^R.

С другой стороны, есть очень простые языки, не имеющие префиксного свойства. Рассмотрим {0}*, т.е. множество всех цепочек из символов 0. Очевидно, в этом языке есть пары цепочек, одна из которых является префиксом другой, так что этот язык не об­ладает префиксным свойством. В действительности, из любых двух цепочек одна являет­ся префиксом другой, хотя это условие и сильнее, чем то, которое нужно для отрицания префиксного свойства. □

Заметим, что язык {0}* регулярен. Таким образом, неверно, что каждый регулярный язык есть N(P) для некоторого ДМП-автомата Р. Оставляем в качестве упражнения сле­дующее утверждение.

Теорема 6.19. Язык L есть N(P) для некоторого ДМП-автомата Р тогда и только тогда, когда L имеет префиксное свойство и L есть ЦР’) для некоторого ДМП-автомата Р’. □

6.4.3. Детерминированные МП-автоматы и КС-языки

Мы уже видели, что ДМП-автоматы могут допускать языки вроде L_smm которые не являются регулярными. Для того чтобы убедиться в его нерегулярности, предположим, что это не так, и используем лемму о накачке. Пусть п — константа из леммы. Рассмот­рим цепочку w = 0^пс0″ из L_wcwr. Если ее «накачивать», изменяется длина первой группы символов 0, и получаются цепочки из L_wcn,_r, у которых «центральный маркер» располо­жен не в центре. Так как эти цепочки не принадлежат L_wcwr, получаем противоречие и де­лаем вывод, что L_wmr нерегулярен.

С другой стороны, существуют КС-языки, вроде £„,„„ которые не могут допускаться по заключительному состоянию никаким ДМП-автоматом. Формальное доказательство весьма сложно, но интуитивно прозрачно. Если Р — ДМП-автомат, допускающий L,„_lr, то при чтении последовательности символов 0 он должен записать их в магазин или сде­лать что-нибудь равносильное для подсчета их количества. Например, записывать один X для каждых 00 на входе и использовать состояние для запоминания четности или нечет­ности числа символов 0.

Предположим, Р прочитал п символов 0 и затем видит на входе 110″. Он должен прове­рить, что после 11 находятся п символов 0, и для этого он должен опустошить свой мага­зин.^[5] Теперь он прочитал 0^П110″. Если далее он видит идентичную цепочку, он должен до­пускать, поскольку весь вход имеет вид ww^R, где w = 0^П110″. Однако если Р видит 0^Ш110^т, где тФп, он должен не допускать. Поскольку его магазин пуст, он не может запомнить, каким было произвольное целое п, и не способен допустить L_mr. Подведем итог.

• Языки, допускаемые ДМП-автоматами по заключительному состоянию, включа­ют регулярные языки как собственное подмножество, но сами образуют собст­венное подмножество КС-языков.

6.4.4. Детерминированные МП-автоматы и неоднозначные грамматики

Мощность ДМП-автоматов можно уточнить, заметив, что все языки, допускаемые ими, имеют однозначные грамматики. К сожалению, класс языков ДМП-автоматов не совпадает с подмножеством КС-языков, не являющихся существенно неоднозначными. Например, L_m„ имеет однозначную грамматику S—> OSO | LSI | £, хотя и не является ДМП-автоматным языком. Следующая теорема уточняет заключительное утверждение из подраздела 6.4.3.

Теорема 6.20. Если L = N(P) для некоторого ДМП-автомата Р, то L имеет однознач­ную КС-грамматику.

Доказательство. Утверждаем, что конструкция теоремы 6.14 порождает однознач­ную КС-грамматику G, когда МП-автомат, к которому она применяется, детерминиро­ван. Вначале вспомним (см. теорему 5.29), что для однозначности грамматики G доста­точно показать, что она имеет уникальные левые порождения.

Предположим, Р допускает w по пустому магазину. Тогда он делает это с помощью одной-единственной последовательности переходов, поскольку он детерминирован и не может работать после опустошения магазина. Зная эту последовательность переходов, мы можем однозначно определить выбор каждой продукции в левом порождении w в G. Правило автомата Р, на основании которого применяется продукция, всегда одно. Но правило, скажем, S(q, а,Х)= {(г, У/У?… У*)}, может порождать много продукций грамма­тики G, с различными состояниями в позициях, отражающих состояния Р после удаления каждого из Yj, У?, …, Y_k. Однако, поскольку Р детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению w. □

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

Теорема 6.21. Если L = L(P) для некоторого ДМП-автомата Р, то L имеет однознач­ную КС-грамматику.

Доказательство. Пусть $ будет «концевым маркером», отсутствующим в цепочках языка L, и пусть L’ = L%. Таким образом, цепочки языка L’ представляют собой цепочки из L, к которым дописан символ $. Тогда L’ имеет префиксное свойство, и по теоре­ме 6.19 L’= N(P^) для некоторого ДМП-автомата Р’.^[6] По теореме 6.20 существует одно­значная грамматика G’, порождающая язык N(P’), т.е. L’.

Теперь по грамматике G’ построим G, для которой L(G) = L. Для этого нужно лишь избавиться от маркера $ в цепочках. Будем рассматривать $ как переменную грамматики G и введем продукцию $ —> £; остальные продукции С и С одинаковы. Поскольку ЦС) = L’ получаем, что L(G) = L.

Утверждаем, что G однозначна. Действительно, левые порождения в G совпадают с левыми порождениями в G\ за исключением последнего шага в G— изменения $ на £. Таким образом, если бы терминальная цепочка w имела два левых порождения в G, то имела бы два порождения в G’. Поскольку Соднозначна, G также однозначна. □

6.4.5. Упражнения к разделу 6.4

Для каждого из следующих МП-автоматов укажите, является ли он детермини­рованным. Либо докажите, что он соответствует определению ДМП-автомата, либо укажите правила, нарушающие его:

а)   МП-автомат из примера 6.2;

б)   (*) МП-автомат из упражнения 6.1.1;

в)   МП-автомат из упражнения 6.3.3.

Постройте ДМП-автомат для каждого из следующих языков:

а)   {0ⁿl^m | п < т}\

б)   {0ⁿl^m \п>т)\

в)   {0″ 1 ^m0ⁿ\ пит произвольны}.

Теорему 6.19 можно доказать с помощью следующих трех шагов:

а)  докажите, что если L = N(P) для некоторого ДМП-автомата Р, то L обладает префиксным свойством;

б)  (!) докажите, что если L = N(P) для некоторого ДМП-автомата Р, то сущест­вует ДМП-автомат Р’, для которого L = L{P’)\

в)   (*!) докажите, что если L обладает префиксным свойством и L = L(P^A) для некоторого ДМП-автомата Р’, то существует ДМП-автомат Р, для которого L = N(P).

(!!) Докажите, что язык

1= {0^ПГ|«> 1} U {0^п1^2п|»> 1}

является КС-языком, не допускаемым ни одним ДМП-автоматом. Указание. До­кажите, что должны существовать две цепочки вида 0^П1^П для различных значе­ний п, скажем, /?, и п₂, чтение которых приводит гипотетический ДМП-автомат для языка L к одному и тому же МО. Интуитивно ДМП-автомат должен удалить из своего магазина почти все, что туда было помещено при чтении символов О, для того, чтобы проверить, что далее читается равное количество символов 1. Таким образом, ДМП-автомат не может решить, следует ли допускать вход, следующий после чтения п, или п₂ символов 1.

Резюме

• Магазинные автоматы. МП-автомат— это недетерминированный конечный автомат с магазином, который может использоваться для запоминания цепочек произвольной длины. Магазин может читаться и изменяться только со стороны его вершины.
• Переходы магазинных автоматов. МП-автомат выбирает следующий переход на основе своего текущего состояния, следующего входного символа и символа на вершине магазина. Он может также выбрать переход, не зависящий от вход­ного символа и без его чтения. Будучи недетерминированным, МП-автомат мо­жет иметь некоторое конечное число выборов перехода; каждый из них состоит из нового состояния и цепочки магазинных символов, заменяющей символ на вершине магазина.
• Допускание магазинными автоматами. Существуют два способа, которыми МП- автомат может сигнализировать допуск. Один заключается в достижении заклю­чительного состояния, другой— в опустошении магазина. Эти способы эквива­лентны в том смысле, что любой язык, допускаемый по одному способу, допуска­ется и по другому (некоторым другим МП-автоматом).
• Мгновенные описания (МО), или конфигурации. Для описания «текущего положе­ния» МП-автомата используется МО, образуемое состоянием, оставшимся входом и содержимым магазина. Отношение переходов (- между МО представляет от­дельные переходы МП-автомата.
• Магазинные автоматы и грамматики. Класс языков, допускаемых МП-авто­матами как по заключительному состоянию, так и по пустому магазину, совпадает с классом КС-языков.
• Детерминированные магазинные автоматы. МП-автомат является детерминиро­ванным, если у него никогда нет выбора перехода для данных состояния, входного символа (включая е) и магазинного символа. У него также нет выбора между пе­реходом с использованием входного символа и переходом без его использования.
• Допускание детерминированными магазинными автоматами. Два способа до- пускания — по заключительному состоянию и по пустому магазину — неэквива­лентны для детерминированных МП-автоматов. Точнее, языки, допускаемые по пустому магазину, — это те, и только те, языки, которые допускаются по заклю­чительному состоянию и обладают префиксным свойством (ни одна цепочка язы­ка не является префиксом другой).
• Языки, допускаемые ДМП-автоматами. Все регулярные языки допускаются (по заключительному состоянию) ДМП-автоматами, и существуют нерегулярные язы­ки, допускаемые ДМП-автоматами. Языки ДМП-автоматов являются контекстно- свободными, причем для них существуют однозначные грамматики. Таким обра­зом, языки ДМП-автоматов лежат строго между регулярными и контекстно- свободными языками.

Литература

Идея магазинного автомата была высказана независимо в работах Эттингера [4] и Шют- ценберже [5]. Установление эквивалентности магазинных автоматов и контекстно-свободных грамматик также явилось результатом независимых исследований; оно было представлено Хомским в техническом отчете МГГ за 1961 г., но впервые было опубликовано в [1].

Детерминированный МП-автомат впервые был предложен Фишером [2] и Шютцен- берже [5]. Позднее он приобрел большое значение как модель синтаксического анализа­тора. Примечательно, что Кнут предложил в [3] «1Л(£)-грамматики», подкласс КС- грамматик, порождающих в точности языки ДМП-автоматов. 1Л(А;)-грамматики, в свою очередь, образуют базис для YACC, инструмента для создания анализаторов, обсуждае­мого в разделе 5.3.2..

1. J. Evey, «Application of pushdown store machines,» Proc. Fall Joint Computer Confer­ence (1963), AFIPS Press, Montvale, NJ, pp. 215-227.
   • Р. С. Fischer, «On computabililty by certain classes of restricted Taring machines,» Fourth Annl. Symposium on Switching Circuit Theory and Logical Design (1963), pp. 23-32.
   • E. Knuth, «On the translation of languages from left to right,» Information and Control 8:6 (1965), pp. 607-639. (Кнут Д. О переводе (трансляции) языков слева направо.— Сб. «Языки и автоматы». — М.: Мир, 1975. — С. 9-42.)
   • G. Oettinger, «Automatic syntactic analysis and pushdown store,» Proc. Symposia on Applied Math. 12 (1961), American Mathematical Society, Providence, RI.
   • P. Schutzenberger, «On context-free languages and pushdown automata,» Information and Control 6:3 (1963), pp. 246-264.

‘ Можно было бы также построить магазинный автомат для L_/Xlh языка, грамматика которого представлена на рис. 5.1. Однако L_wr несколько проще и позволит нам сосредоточиться на идеях, касающихся магазинных автоматов.

^[2] Символ N в N(P) обозначает «пустой магазин» («null stack»). 244   ГЛАВА 6. АВТОМАТЫ С МАГАЗИННОЙ ПАМЯТЬЮ

^[3] Не обращайте внимания на то, что тут использованы новые состояния риг, хотя в конструк­ции теоремы 6.9 указаны р₀ и p_f. Имена состояний могут быть совершенно произвольными.

^[4] Хотя а может быть е, и в этом случае P_F опустошает свой магазин и одновременно допус­кает.

^[5] Это интуитивное утверждение требует сложного формального доказательства; возможен ли другой способ для Р сравнить два равных блока символов 0?

^[6] Доказательство теоремы 6.19 возникает в упражнении 6.4.3, но построение Р’по Р несложно. Добавим новое состояние су, в которое переходит /» если Р перешел в заключительное состояние и следующим входным символом является $. Находясь в состоянии q, Р’выталкивает все символы из магазина. Кроме того, для Р’нужен дополнительный маркер дна магазина, чтобы избежать слу­чайного опустошения магазина при имитации Р.