Введение в теорию автоматов, языков и вычислений. Глава 6.


ГЛАВА 6

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

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

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

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

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

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

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

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

Конечное управление
Вход
Допустить/отвергнуть

Магазин

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 6.2. Построим МП-автомат Р, допускающий язык Lm„ из примера 6.1. Вна­чале уточним одну деталь, необходимую для правильной организации работы с магази­ном. Магазинный символ Z0 используется для отметки дна магазина. Этот символ дол­жен присутствовать в магазине, чтобы, удалив из магазина w и обнаружив на входе wwR, можно было совершить переход в допускающее состояние q2. Итак, наш МП-автомат для языка Lm„ можно представить в следующем виде.

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

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

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

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

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

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

  • z0/oz0
  • z0/iz0 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, q0, Z0, F) — МП-автомат. Определим отношение (-, или просто

р

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

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

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

  • *

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

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

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

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

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

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

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

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

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

(q0, 111, 1 Zo) h (Чо, 11, 1 iZ0) h (ЧП, 1 Ш h (Чи 1, IZo) h (Чь e, Z0) |- (g2, e, Z0). □

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

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

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

(q,,E,llllZ0) (qpE.UZj)                 (qpE.Ze)

‘ r

(q2.Ezo)

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

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

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

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

Теорема 6.5. Если Р = (Q, Е, Г, <5, q0, Z0, 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, q0, Z0, F) — МП-автомат и (q, xw, а) (р, yw, р), то верно также, что (q, х, а) (- (р, у, р). □

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

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

  1. 8(q,0,Z0)={(q,XZ0)}. 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, Z0), если входным словом w является:

а)   01;

б)   0011; в) 010.

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

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

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

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

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

{w | (q0, w, Z0) ^ (q, £, a)}

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

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

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

(q0, wwR, Z0) \-(q0, wR, wRZ0) |- (qh wR, wRZ0) \-(qt, £, Z0) |- (q2, £, Z0) Таким образом, МП-автомат имеет возможность прочитать цепочку w на входе и запи­сать ее символы в свой магазин в обратном порядке. Затем он спонтанно переходит в со­стояние qi и проверяет совпадение wR на входе с такой же цепочкой в магазине, и нако­нец, спонтанно переходит в состояние q2.

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

  • Если (q0, х, a) j- (q,, е, а), то х имеет вид wwR.

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

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

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

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

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

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

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

(Яо, а2…а„, а,а) |- (qh а„, а,а)


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

(q0, а2…а„.,, а,а) |- (qh £, а,а) Поскольку вход у этой последовательности короче, чем п, можно применить индук­тивное предположение и заключить, что а2…ап., имеет вид »,R для некоторого у. Поскольку х = а/ууяа„, и нам известно, что at = а„, делаем вывод, что х имеет вид mvR; в частности w = а }у.

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

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

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

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

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

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

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

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

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

Теорема 6.9. Если L = N(Pn) для некоторого МП-автомата PN = (Q, Е, Г, SN, q0, Z0), то существует такой МП-автомат PF, у которого L = L(P,.).

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

е,Х0

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

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

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

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

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

F,-

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

р»

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

(ро, w,X0) |- (q0, w, ZoXo) |- (q, e,X0) |- (pf, e, e)                                 (6.1)

pf                                          pf                               pe

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

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

Таким образом, любое вычисление в автомате / /.. допускающее w, должно выглядеть как последовательность (6.1). Более того, середина вычисления (все переходы, кроме первого и последнего) должна также быть вычислением в PN с Х0 под магазином. Это обусловлено тем, что, за исключением первого и последнего шагов, PF не может исполь­зовать переходы, которые не являются переходами PN, и Х„ не может оказаться на вер­шине магазина (иначе вычисление заканчивалось бы на следующем шаге). Таким обра­зом, (q0, w, Z0) |- (q, £, е), и w G N(Pn). □ рк

Пример 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 больше, чем е. В частности, если магазин пуст, то символов е прочитано на один больше, чем /, и входная последовательность недопустима в С-прог-
рамме. Именно такие цепочки наш МП-автомат PN допускает по пустому магазину. Его формальное определение имеет следующий вид.

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

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

e,Zle i.ZIZZ

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

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

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

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

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

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

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

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

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

Теорема 6.11. Пусть L = L(PF) для некоторого МП-автомата PF = (Q, Е, Г, SF, q0, Z0, F). Тогда существует такой МП-автомат PN, у которого L = N(Pn). Доказательство. Конструкция соответствует рис. 6.7. Пусть

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

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

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

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

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

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

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

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

р,

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

*

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

P.V

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

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

ps

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

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

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

Р»                         Р»                      Рх

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

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

Pf

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

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

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

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

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

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

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

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

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

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

а)  {d&ck | или j * к];

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

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

8(q0, a, Z0) = {q,, AAZ„) 8{q0, b, Z„) = (q2, BZ0) 8(q0, e, Z0) = (/,£) 8{qh a, A) = (qh AAA) 8{qh b, A) = {qh s) 8(qh £, Z0) = {q0, Z0) S(q2, a, B) = (q3, £)   8(q2, b, B) = (q2, BB) S(q2, £, Z0) = (qlh Z0)

8(q3, £, B) = (q2, £)                 8(q3, £, Z0) = (qh AZ0)

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

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

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

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

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

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

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

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

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

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

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

Щ>з) = 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,yhi, <*;/)• Поскольку а, является остатком, он начинается переменной А. Кроме того, шаг порождения у, => у,; включает замену переменной А од-

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

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

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

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

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

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

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

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

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

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

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

Рис. 6.9. МП-автомат А прочитывает х и удаляет ВаС из своего магазина

*

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

Если Y, — терминал, то должен совершаться только один переход, в котором прове­ряется совпадение х, и У,. Опять-таки, можно сделать вывод, что Yt => х,; на этот раз по­рождение пустое. Теперь у нас есть порождение

А => Y,Y2…Yk => x,Y2…Yk => … => х,х2…хк. *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[qXrk] ^ a[rY,r,][г,Y2r2)…[rk lYkrk].

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

Докажем корректность неформальной интерпретации переменных вида [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, либо е. Отсюда следу­ет, что пара (r0, Y/Y2…Yk) должна быть в S(q, а,Х). Кроме того, по построению G сущест­вует продукция [qXrk] a[rf)Ytr,}\rtГ,/-,]…[rk ,Ykrk], у которой rk= р и п, г2, …,гк , — не­которые состояния из Q.

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

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

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

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

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

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

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

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

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

*

[qXrt] => a[r0Y,r,][r,Y2r2]…[rk_,Y^k] => w Здесь гк = р. Эта продукция должна быть в грамматике, так как (r0, YiY2…Yk) есть в 8(q, а, X).

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

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

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

(n-hWiW^,…wk, Y,Yj,,…Yk) f- (r„w,4…wk, Y,.,…Yk).

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

*

(q,2L-w,w2…wk,X) (r0,w,w2…wk, Y,Y2…Yk) \-

* * *

(rhw2w3…wk, Y2Y3…Yk) \- (r2,w3…wk, Y3…Yk) … (rk, £, £) Поскольку rk = p, мы доказали, что (q, w, X) (p, e, e).

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

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

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

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

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

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

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

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

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

  1. Из того, что 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, Z0}, д, q, Z0) в КС-грамма- тику, где д задана следующим образом.
    1. S(q,l,Z0) = {(q,XZ0)}.
    2. S(q,l,X)={(q,XX)}.
    3. S(q,£,X)={(q,e)).
    4. Sip, l,X) = {(p,e)}.
    5. Sip,0,Z0) = {(q,Z0)}.
  • Преобразуйте МП-автомат из упражнения 6.1.1 в КС-грамматику.
  • Ниже приведены КС-языки. Постройте для каждого из них МП-автомат, допус­кающий этот язык по пустому магазину. При желании можно сначала построить КС-грамматику для этого языка, а затем преобразовать ее в МП-автомат.

а)   {an6mc2(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, q0, 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’cvvR I we (0 + 1)*}, распознаваемый некоторым ДМП-автоматом.

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

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

  • z0/oz0
  • ze/ize 0,0/00 0,1/01

1,0/10          0,0/е

1,1/11         1,1/Е

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

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

с, z0/z0               е, Z0/Z0

с, 0/0

с, 1/1

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

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

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

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

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

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

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

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

Пример 6.18. Язык L,mr из примера 6.16 имеет префиксное свойство, т.е. в нем не может быть двух разных цепочек wc\vK и xcxR, одна из которых является префиксом дру­гой. Чтобы убедиться в этом, предположим, что wcwR — префикс jcccr, и и’ Ф х. Тогда w должна быть короче, чем х. Следовательно, с в w приходится на позицию, в которой л: имеет 0 или 1, а это противоречит предположению, что wcwR — префикс xcxR.

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

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

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

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

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

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

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

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

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

Мощность ДМП-автоматов можно уточнить, заметив, что все языки, допускаемые ими, имеют однозначные грамматики. К сожалению, класс языков ДМП-автоматов не совпадает с подмножеством КС-языков, не являющихся существенно неоднозначными. Например, Lm„ имеет однозначную грамматику 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, У?, …, Yk. Однако, поскольку Р детерминирован, осуществляется только одна из этих последовательностей переходов, поэтому только одна из этих продукций в действительности ведет к порождению 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.

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

а)   {0nlm | п < т}\

б)   {0nlm \п>т)\

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

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

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

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

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

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

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

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

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

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

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

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

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