Выталкивающий автомат - Pushdown automaton

Классы автоматов

(При нажатии на каждый слой открывается статья на эту тему)

В теории вычислений , разделе теоретической информатики , автомат выталкивания ( КПК ) - это тип автомата, который использует стек .

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

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

Неформальное описание

Схема выталкивающего автомата

Конечный автомат просто смотрит на входной сигнал и текущее состояние: оно не имеет стек для работы с. Он выбирает новое состояние, результат следования за переходом. Магазинный автомат (PDA) отличается от конечного автомата двумя способами:

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

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

Сложить вместе: учитывая входной символ, текущее состояние и символ стека, автомат может следовать переходу в другое состояние и при необходимости манипулировать стеком (толкать или выталкивать).

Если в каждой ситуации возможно не более одного такого переходного действия, то автомат называется детерминированным автоматом выталкивания (DPDA) . В общем случае, если возможны несколько действий, автомат называется общим , или недетерминированным , КПК . Данная входная строка может привести недетерминированный автомат выталкивания к одной из нескольких последовательностей конфигурации; если один из них приводит к принятию конфигурации после прочтения всей входной строки, последняя считается принадлежащей к языку, принятому автоматом .

Формальное определение

Мы используем стандартные обозначения формального языка: обозначает набор строк конечной длины по алфавиту и обозначает пустую строку . ${\ displaystyle \ Gamma ^ {*}}$ ${\ displaystyle \ Gamma}$ ${\ Displaystyle \ varepsilon}$

КПК формально определяется как набор из семи элементов:

${\ Displaystyle M = (Q, \ Sigma, \ Gamma, \ delta, q_ {0}, Z, F)}$ куда

${\ displaystyle Q}$ конечный набор состояний
${\ displaystyle \ Sigma}$ конечное множество, которое называется входным алфавитом
${\ displaystyle \ Gamma}$ - конечное множество, которое называется стековым алфавитом.
${\ displaystyle \ delta}$ является конечным подмножеством , переходное отношение ${\ displaystyle Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma \ times Q \ times \ Gamma ^ {*}}$
${\ displaystyle q_ {0} \ in Q}$ это начальное состояние
${\ Displaystyle Z \ in \ Gamma}$ это начальный символ стека
${\ Displaystyle F \ substeq Q}$ это набор принимающих состояний

Элемент - это переход . Он имеет предполагаемое значение, что в состоянии , на входе и с самым верхним символом стека, он может читать , изменять состояние на , выталкивать, заменяя его нажатием . Компонент переходного соотношения используется для формализации , что КПК может либо прочитать письмо от входа, или перейти оставляя вход нетронутым. ${\ Displaystyle (п, а, А, д, \ альфа) \ в \ дельта}$ ${\ displaystyle M}$ ${\ displaystyle M}$ ${\ displaystyle p \ in Q}$ ${\ displaystyle a \ in \ Sigma \ cup \ {\ varepsilon \}}$ ${\ displaystyle A \ in \ Gamma}$ ${\ displaystyle a}$ ${\ displaystyle q}$ ${\ displaystyle A}$ ${\ displaystyle \ alpha \ in \ Gamma ^ {*}}$ ${\ Displaystyle (\ Sigma \ чашка \ {\ varepsilon \})}$

Во многих текстах отношение перехода заменено (эквивалентной) формализацией, где

${\ displaystyle \ delta}$ - функция перехода , отображаемая в конечные подмножества ${\ Displaystyle Q \ раз (\ Сигма \ чашка \ {\ varepsilon \}) \ раз \ Гамма}$ ${\ Displaystyle Q \ times \ Gamma ^ {*}}$

Здесь собраны все возможные действия в состоянии с в стеке при чтении на входе. Например, пишут именно когда, потому что . Отметим, что конечность в этом определении существенна. ${\ displaystyle \ delta (p, a, A)}$ ${\ displaystyle p}$ ${\ displaystyle A}$ ${\ displaystyle a}$ ${\ Displaystyle \ дельта (п, а, А) = \ {(д, ВА) \}}$ ${\ displaystyle (q, BA) \ in \ {(q, BA) \}, (q, BA) \ in \ delta (p, a, A),}$ ${\ Displaystyle ((п, а, А), \ {(д, ВА) \}) \ в \ дельта}$

Расчеты

шаг выталкивающего автомата

С целью формализации семантики автомата проталкивания вводится описание текущей ситуации. Любая тройка называется мгновенным описанием (ID) , которое включает в себя текущее состояние, часть входной ленты, которая не была прочитана, и содержимое стека (самый верхний символ, записанный первым). Переход отношение определяет ступенчатые отношения с на мгновенных описаниях. Для инструкции существует шаг , для каждого и каждого . ${\ Displaystyle (п, ш, \ бета) \ в Q \ times \ Sigma ^ {*} \ times \ Gamma ^ {*}}$ ${\ displaystyle M}$ ${\ displaystyle \ delta}$ ${\ displaystyle \ vdash _ {M}}$ ${\ displaystyle M}$ ${\ Displaystyle (п, а, А, д, \ альфа) \ в \ дельта}$ ${\ Displaystyle (п, топор, А \ гамма) \ vdash _ {M} (д, х, \ альфа \ гамма)}$ ${\ Displaystyle х \ in \ Sigma ^ {*}}$ ${\ displaystyle \ gamma \ in \ Gamma ^ {*}}$

В общем, автоматические выталкивающие машины недетерминированы, что означает, что в данном мгновенном описании может быть несколько возможных шагов. Любой из этих шагов может быть выбран в вычислении. С приведенным выше определением на каждом шаге всегда выскакивает один символ (верх стека), заменяя его необходимым количеством символов. Как следствие, шаг не определяется, когда стек пуст. ${\ Displaystyle (п, ш, \ бета)}$

Вычисления автомата выталкивания представляют собой последовательность шагов. Вычисление начинается в начальном состоянии с начальным символом стека в стеке и строкой на входной ленте, то есть с начальным описанием . Есть два режима принятия. Автомат выталкивания либо принимает конечное состояние, что означает, что после чтения своего ввода автомат достигает состояния приема (in ), либо принимает пустым стеком ( ), что означает, что после чтения своего ввода автомат опустошает свой стек. Первый режим приема использует внутреннюю память (состояние), второй - внешнюю память (стек). ${\ displaystyle q_ {0}}$ ${\ displaystyle Z}$ ${\ displaystyle w}$ ${\ displaystyle (q_ {0}, ш, Z)}$ ${\ displaystyle F}$ ${\ Displaystyle \ varepsilon}$

Формально определяется

${\ Displaystyle L (M) = \ {вес \ in \ Sigma ^ {*} | (q_ {0}, w, Z) \ vdash _ {M} ^ {*} (f, \ varepsilon, \ gamma)}$ с и (конечное состояние) ${\ displaystyle f \ in F}$ ${\ displaystyle \ gamma \ in \ Gamma ^ {*} \}}$
${\ Displaystyle N (M) = \ {вес \ in \ Sigma ^ {*} | (q_ {0}, w, Z) \ vdash _ {M} ^ {*} (q, \ varepsilon, \ varepsilon)}$ с (пустой стек) ${\ displaystyle q \ in Q \}}$

Здесь представлено рефлексивное и транзитивное замыкание шагового отношения, означающее любое количество последовательных шагов (ноль, один или несколько). ${\ displaystyle \ vdash _ {M} ^ {*}}$ ${\ displaystyle \ vdash _ {M}}$

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

Теорема. Для каждого автомата выталкивания можно построить автомат выталкивания так , что , и наоборот, для каждого автомата выталкивания можно построить автомат выталкивания, такой что ${\ displaystyle M}$ ${\ displaystyle M '}$ ${\ Displaystyle L (М) = Н (М ')}$ ${\ displaystyle M}$ ${\ displaystyle M '}$ ${\ Displaystyle Н (М) = L (М ')}$

Пример

Ниже приводится формальное описание КПК, распознающего язык по конечному состоянию: ${\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}$

КПК для (по конечному состоянию)

{\ displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}

${\ Displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ Z, \ F)}$ , куда

состояния: ${\ Displaystyle Q = \ {p, q, r \}}$
входной алфавит: ${\ Displaystyle \ Sigma = \ {0,1 \}}$
сложить алфавит: ${\ Displaystyle \ Gamma = \ {A, Z \}}$
начальное состояние: ${\ displaystyle q_ {0} = p}$
символ начала стека: $Z$
принимающие государства: ${\ Displaystyle F = \ {г \}}$

Отношение перехода состоит из следующих шести инструкций: ${\ displaystyle \ delta}$

{\ displaystyle (p, 0, Z, p, AZ)}

,

{\ displaystyle (p, 0, A, p, AA)}

,

{\ displaystyle (p, \ epsilon, Z, q, Z)}

,

{\ displaystyle (p, \ epsilon, A, q, A)}

,

{\ displaystyle (q, 1, A, q, \ epsilon)}

, а также

{\ displaystyle (q, \ epsilon, Z, r, Z)}

.

На словах первые две инструкции говорят, что в состоянии $p в$ любое время символ0 читается, один $A$ помещается в стек. Размещение символа $A$ поверх другого $A$ формализуется как замена вершины $A$ на $AA$ (и аналогично для нажатия символа $A$ поверх $Z$ ).

Третья и четвертая инструкции говорят, что в любой момент автомат может перейти из состояния $p$ в состояние $q$ .

Пятая инструкция говорит, что в состоянии $q$ для каждого символа1 прочитал, выскочил один $A.$

И, наконец, шестая инструкция говорит , что машина может перейти от состояния $д$ до принятия состояния $г$ только тогда , когда стек состоит из одного $Z$ .

Вроде бы нет общепринятого представления для КПК. Здесь мы изобразили инструкцию переходом от состояния $p$ к состоянию $q,$ помеченным (прочтите $a$ ; замените $A$ на ). ${\ Displaystyle (п, а, А, д, \ альфа)}$ ${\ displaystyle a; A / \ alpha}$ ${\ displaystyle \ alpha}$

Понимание вычислительного процесса

принятие вычислений для 0011

Ниже показано, как указанный выше КПК вычисляет различные входные строки. Нижний индекс $M$ символа шага здесь опущен. ${\ displaystyle \ vdash}$

Входная строка = 0011. Существуют различные вычисления, в зависимости от момента перехода из состояния p в состояние q . Только один из них принимает.
1. ${\ displaystyle (p, 0011, Z) \ vdash (q, 0011, Z) \ vdash (r, 0011, Z)}$
  Конечным состоянием является принятие, но ввод таким образом не принимается, так как он не был прочитан.
2. ${\ displaystyle (p, 0011, Z) \ vdash (p, 011, AZ) \ vdash (q, 011, AZ)}$
  Дальнейшие шаги невозможны.
3. ${\ displaystyle (p, 0011, Z) \ vdash (p, 011, AZ) \ vdash (p, 11, AAZ) \ vdash (q, 11, AAZ) \ vdash (q, 1, AZ) \ vdash (q , \ epsilon, Z) \ vdash (r, \ epsilon, Z)}$
  Принятие вычисления: завершается в состоянии принятия, в то время как полный ввод был прочитан.
Строка ввода = 00111. Опять же, есть разные вычисления. Ни один из них не принимает.
1. ${\ displaystyle (p, 00111, Z) \ vdash (q, 00111, Z) \ vdash (r, 00111, Z)}$
  Конечным состоянием является принятие, но ввод таким образом не принимается, так как он не был прочитан.
2. ${\ displaystyle (p, 00111, Z) \ vdash (p, 0111, AZ) \ vdash (q, 0111, AZ)}$
  Дальнейшие шаги невозможны.
3. ${\ displaystyle (p, 00111, Z) \ vdash (p, 0111, AZ) \ vdash (p, 111, AAZ) \ vdash (q, 111, AAZ) \ vdash (q, 11, AZ) \ vdash (q , 1, Z) \ vdash (r, 1, Z)}$
  Конечным состоянием является принятие, но ввод таким образом не принимается, так как он не был (полностью) прочитан.

КПК и контекстно-свободные языки

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

Технически, учитывая контекстно-свободную грамматику, КПК имеет единственное состояние, 1, и его отношение перехода строится следующим образом.

${\ displaystyle (1, \ varepsilon, A, 1, \ alpha)}$ для каждого правила ( развернуть ) ${\ Displaystyle от А \ до \ альфа}$
${\ Displaystyle (1, а, а, 1, \ varepsilon)}$ для каждого терминального символа ( совпадение ) ${\ displaystyle a}$

КПК принимает пустой стек. Его начальный символ стека - это начальный символ грамматики.

Для контекстно-свободной грамматики в нормальной форме Грейбаха определение (1, γ) ∈ δ (1, a , A ) для каждого правила грамматики A → a γ также дает эквивалентный недетерминированный автомат выталкивания.

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

Теорема. Для каждого автомата выталкивания можно построить контекстно-свободную грамматику, такую что . ${\ displaystyle M}$ ${\ displaystyle G}$ ${\ Displaystyle N (M) = L (G)}$

Язык строк, принимаемый детерминированным автоматом выталкивания, называется детерминированным контекстно-свободным языком . Не все контекстно-свободные языки детерминированы. Как следствие, DPDA является строго более слабым вариантом КПК, и не существует алгоритма преобразования КПК в эквивалентный DPDA, если такой DPDA существует.

Конечный автомат с доступом к двум стекам - более мощное устройство, эквивалентное по мощности машине Тьюринга . Линейный ограниченный автомат представляет собой устройство , которое является более мощным , чем магазинный автомат , но в меньшей степени, чем машина Тьюринга.

КПК и машины Тьюринга

Автомат выталкивания в вычислительном отношении эквивалентен «ограниченной» машине Тьюринга (TM) с двумя лентами, которая ограничена следующим образом: на первой ленте TM может только читать ввод и перемещаться слева направо (он не может вносить изменения) . На второй ленте он может только «проталкивать» и «выталкивать» данные. Или, что эквивалентно, он может читать, писать и перемещаться влево и вправо с ограничением, что единственное действие, которое он может выполнять на каждом шаге, - это либо удаление самого левого символа в строке (pop), либо добавление дополнительного символа слева к самому левому символ в строке (push).

То, что КПК слабее TM, можно свести к тому, что процедура pop удаляет некоторые данные. Чтобы КПК был таким же сильным, как TM, нам нужно где-то сохранять данные, потерянные из-за «всплывающего окна». Мы можем добиться этого, введя второй стек. В модели TM КПК из последнего абзаца это эквивалентно TM с 3 лентами, где первая лента является входной лентой только для чтения, а 2-я и 3-я ленты являются лентами «push and pop» (стопка). Чтобы такой КПК мог имитировать любую заданную ТМ, мы передаем вход КПК на первую ленту, при этом оба стека остаются пустыми. Затем он перемещает весь ввод с входной ленты в первый стек. Когда весь ввод передается в 1-й стек, теперь мы действуем как обычная TM, где движение прямо по ленте аналогично извлечению символа из 1-го стека и перемещению (возможно обновленного) символа во второй стек, и перемещение влево соответствует выталкиванию символа из 2-го стека и помещению (возможно обновленного) символа в первую стопку. Таким образом, у нас есть КПК с 2 стеками, который может имитировать любую TM.

Обобщенный автомат выталкивания (GPDA)

GPDA - это КПК, который записывает всю строку известной длины в стек или удаляет всю строку из стека за один шаг.

GPDA формально определяется как кортеж из 6:

{\ Displaystyle M = (Q, \ \ Sigma, \ \ Gamma, \ \ delta, \ q_ {0}, \ F)}

где , и определяются так же, как и КПК. ${\ Displaystyle Q, \ Sigma \ ,, \ Gamma \ ,, q_ {0}}$ ${\ displaystyle F}$

{\ displaystyle \, \ delta}

:

{\ Displaystyle Q \ times \ Sigma _ {\ epsilon} \ times \ Gamma ^ {*} \ longrightarrow P (Q \ times \ Gamma ^ {*})}

- функция перехода.

Правила вычислений для GPDA такие же, как и для КПК, за исключением того, что 's и ' теперь являются строками, а не символами. ${\ displaystyle a_ {я + 1}}$ ${\ displaystyle b_ {я + 1}}$

GPDA и КПК эквивалентны в том смысле, что если язык распознается КПК, он также распознается GPDA, и наоборот.

Можно сформулировать аналитическое доказательство эквивалентности GPDA и КПК, используя следующую симуляцию:

Пусть будет переход GPDA ${\ displaystyle \ delta (q_ {1}, w, x_ {1} x_ {2} \ cdot x_ {m}) \ longrightarrow (q_ {2}, y_ {1} y_ {2} ... y_ {n })}$

где . ${\ displaystyle q_ {1}, q_ {2} \ in Q, w \ in \ Sigma _ {\ epsilon}, x_ {1}, x_ {2}, \ ldots, x_ {m} \ in \ Gamma ^ { *}, m \ geq 0, y_ {1}, y_ {2}, \ ldots, y_ {n} \ in \ Gamma ^ {*}, n \ geq 0}$

Постройте для КПК следующие переходы:

{\ displaystyle {\ begin {array} {lcl} \ delta '(q_ {1}, w, x_ {1}) & \ longrightarrow & (p_ {1}, \ epsilon) \\\ delta' (p_ {1 }, \ epsilon, x_ {2}) & \ longrightarrow & (p_ {2}, \ epsilon) \\ & \ vdots & \\\ delta '(p_ {m-1}, \ epsilon, x_ {m}) & \ longrightarrow & (p_ {m}, \ epsilon) \\\ delta '(p_ {m}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m + 1}, y_ {n}) \\\ delta '(p_ {m + 1}, \ epsilon, \ epsilon) & \ longrightarrow & (p_ {m + 2}, y_ {n-1}) \\ & \ vdots & \\\ delta' (p_ {m + n-1}, \ epsilon, \ epsilon) & \ longrightarrow & (q_ {2}, y_ {1}) \ end {array}}}

Стек автомат

В качестве обобщения автоматов выталкивания, Гинзбург, Грейбах и Харрисон (1967) исследовали стековые автоматы , которые могут дополнительно шагать влево или вправо во входной строке (окруженные специальными символами концевых маркеров, чтобы предотвратить выскальзывание), и шагать вверх или вниз в строке ввода. стек в режиме только для чтения. Автомат стека называется не стирающимся, если он никогда не появляется из стека. Класс языков, принимаемых недетерминированными, нестирающими стековыми автоматами, - это NSPACE ( n ² ), который является надмножеством контекстно-зависимых языков . Класс языков, принимаемых детерминированными, нестирающими стековыми автоматами, - это DSPACE ( n ⋅log ( n )).

Чередующиеся выталкивающие автоматы

Переменного магазинный автомат (APDA) представляет собой магазинный автомат с множеством состояний

${\ Displaystyle Q = Q _ {\ exists} \ cup Q _ {\ forall}}$ где . ${\ Displaystyle Q _ {\ существует} \ cap Q _ {\ forall} = \ emptyset}$

Состояния в и называются экзистенциальными соотв. универсальный . В экзистенциальном состоянии APDA недетерминированно выбирает следующее состояние и принимает его, если принимает хотя бы одно из результирующих вычислений. В универсальном состоянии APDA переходит ко всем следующим состояниям и принимает, если все результирующие вычисления принимают. ${\ Displaystyle Q _ {\ существует}}$ ${\ displaystyle Q _ {\ forall}}$

Модель была представлена Chandra , Kozen и Stockmeyer . Ладнер , Липтон и Стокмейер доказали, что эта модель эквивалентна EXPTIME, т.е. язык принимается некоторым APDA тогда и только тогда , когда он может быть определен с помощью алгоритма экспоненциального времени.

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

Смотрите также

Примечания

использованная литература

^ ^a ^b ^c Джон Э. Хопкрофт; Джеффри Д. Ульман (1967). «Неизменные стековые автоматы» . Журнал компьютерных и системных наук . 1 (2): 166–186. DOI : 10.1016 / s0022-0000 (67) 80013-8 .
^ ^a ^b ^c ^d ^e ^е Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг / МА: Аддисон-Уэсли. ISBN 0-201-02988-X.
^ Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: раздел 6.4.3, стр.249
^ Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Стек-автоматы и компиляция». J. ACM . 14 (1): 172–201. DOI : 10.1145 / 321371.321385 .
^ Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Односторонние стековые автоматы». J. ACM . 14 (2): 389–418. DOI : 10.1145 / 321386.321403 .
^ Чандра, Ашок К .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование». Журнал ACM . 28 (1): 114–133. DOI : 10.1145 / 322234.322243 . ISSN 0004-5411 .
^ Ladner, Ричард Э .; Липтон, Ричард Дж .; Стокмейер, Ларри Дж. (1984). «Чередование автоматов выталкивания и стека». SIAM Journal on Computing . 13 (1): 135–155. DOI : 10.1137 / 0213010 . ISSN 0097-5397 .
^ Айзиковиц, Тамар; Камински, Майкл (2011). "LR (0) Конъюнктивные грамматики и детерминированные синхронизированные чередующиеся автоматические выталкивания". Информатика - теория и приложения . Конспект лекций по информатике. 6651 . С. 345–358. DOI : 10.1007 / 978-3-642-20712-9_27 . ISBN 978-3-642-20711-2. ISSN 0302-9743 .

Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X. Раздел 2.2: Автоматические отжимания, стр. 101–114.
Жан-Мишель Отбер, Жан Берстель, Люк Боассон, Контекстно-свободные языки и автоматические механизмы, в: Г. Розенберг, А. Саломаа (ред.), Справочник по формальным языкам, Том. 1, Springer-Verlag, 1997, 111–174.

внешние ссылки

JFLAP , симулятор для нескольких типов автоматов, включая недетерминированные автоматы выталкивания
CoAn , еще один симулятор для нескольких типов машин, включая недетерминированные автоматы с выталкиванием (C ++, Windows, Linux, MacOS)

[Hopcroft.Ullman.1967-1] Джон Э. Хопкрофт; Джеффри Д. Ульман (1967). «Неизменные стековые автоматы» . Журнал компьютерных и системных наук . 1 (2): 166–186. DOI : 10.1016 / s0022-0000 (67) 80013-8 .

[Hopcroft.Ullman.1979-2] е Джон Э. Хопкрофт и Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг / МА: Аддисон-Уэсли. ISBN 0-201-02988-X.

[3] Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Ульман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: раздел 6.4.3, стр.249

[6] Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Стек-автоматы и компиляция». J. ACM . 14 (1): 172–201. DOI : 10.1145 / 321371.321385 .

[7] Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Односторонние стековые автоматы». J. ACM . 14 (2): 389–418. DOI : 10.1145 / 321386.321403 .

[ChandraKozen1981-8] Чандра, Ашок К .; Kozen, Dexter C .; Стокмейер, Ларри Дж. (1981). «Чередование». Журнал ACM . 28 (1): 114–133. DOI : 10.1145 / 322234.322243 . ISSN 0004-5411 .

[LadnerLipton1984-9] Ladner, Ричард Э .; Липтон, Ричард Дж .; Стокмейер, Ларри Дж. (1984). «Чередование автоматов выталкивания и стека». SIAM Journal on Computing . 13 (1): 135–155. DOI : 10.1137 / 0213010 . ISSN 0097-5397 .

[AizikowitzKaminski2011-10] Айзиковиц, Тамар; Камински, Майкл (2011). "LR (0) Конъюнктивные грамматики и детерминированные синхронизированные чередующиеся автоматические выталкивания". Информатика - теория и приложения . Конспект лекций по информатике. 6651 . С. 345–358. DOI : 10.1007 / 978-3-642-20712-9_27 . ISBN 978-3-642-20711-2. ISSN 0302-9743 .

Languages

In other projects