Нажимной автомат

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

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

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

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

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

Неофициальное описание

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

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

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

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

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

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

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

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

$M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)$ где

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

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

Во многих текстах ^[2]^: 110 отношение перехода заменяется (эквивалентной) формализацией, где

$\delta$ — функция перехода , отображающая $Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma$ на конечные подмножества $Q\times \Gamma ^{*}$

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

Вычисления

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

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

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

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

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

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

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

Теорема. Для каждого понижающего автомата $M$ можно построить автомат с выталкивающим устройством $M'$ такой, что $L(M)=N(M')$ , и наоборот, для каждого автомата с понижающей передачей $M$ можно построить автомат с выталкивающим устройством $M'$ такой, что $N(M)=L(M')$

Пример

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

КПК для $\{0^{n}1^{n}\mid n\geq 0\}$
(по окончательному состоянию)

$M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)$ , где

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

Переходное отношение $\delta$ состоит из следующих шести инструкций:

(p,0,Z,p,AZ)

,

(p,0,A,p,AA)

,

(p,\epsilon ,Z,q,Z)

,

(p,\epsilon ,A,q,A)

,

(q,1,A,q,\epsilon )

, и

(q,\epsilon ,Z,r,Z)

.

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

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

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

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

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

Объяснение

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

Входная строка = 0011. В зависимости от момента перехода из состояния p в состояние q выполняются различные вычисления. Только один из них принимает.
1. $(p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)$
  Конечное состояние — принятие, но ввод не принимается таким образом, поскольку он не был прочитан.
2. $(p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)$
  Дальнейшие действия невозможны.
3. $(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. $(p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)$
  Конечное состояние — принятие, но ввод не принимается таким образом, поскольку он не был прочитан.
2. $(p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)$
  Дальнейшие действия невозможны.
3. $(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)$
  Конечное состояние — принятие, но ввод не принимается таким образом, поскольку он не был (полностью) прочитан.

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

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

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

$(1,\varepsilon ,A,1,\alpha )$ для каждого правила $A\to \alpha$ ( расширять )
$(1,a,a,1,\varepsilon )$ для каждого символа терминала $a$ ( соответствовать )

КПК принимает пустой стек. Его начальный символ стека является начальным символом грамматики. ^[3]

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

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

Теорема. Для каждого понижающего автомата $M$ можно построить контекстно-свободную грамматику $G$ такой, что $N(M)=L(G)$ . ^[2]^: 116

Язык строк, принимаемый детерминированным автоматом с выталкиванием (DPDA), называется детерминированным контекстно-свободным языком . Не все контекстно-свободные языки являются детерминированными. ^{[примечание 1]} Как следствие, DPDA является строго более слабым вариантом PDA. Даже для обычных языков существует проблема резкого увеличения размера: для любой рекурсивной функции $f$ и для сколь угодно больших целых чисел $n$ , есть КПК размером $n$ описание обычного языка, наименьший DPDA которого имеет как минимум $f(n)$ государства. ^[5] Для многих нерегулярных КПК любой эквивалентный DPDA потребует неограниченного числа состояний.

Конечный автомат с доступом к двум стекам — более мощное устройство, эквивалентное по мощности машине Тьюринга . ^[2]^: 171 Линейный ограниченный автомат — это устройство, которое более мощно, чем автомат с выталкиванием, но уступает машине Тьюринга. ^{[примечание 2]}

Машины Тьюринга

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

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

Обобщение

Обобщенный автомат с выталкиванием вниз (GPDA) — это КПК, который записывает в стек всю строку некоторой известной длины или удаляет всю строку из стека за один шаг.

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

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

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

\,\delta

:

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

является функцией перехода.

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

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

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

Позволять $\delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})$ быть переходом GPDA

где $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$ .

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

{\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) исследовали стековые автоматы , которые могут дополнительно делать шаг влево или вправо во входной строке (окруженный специальными символами конечного маркера для предотвращения выскальзывания), а также шагать вверх или вниз по входной строке. стек в режиме только для чтения. ^[6]^[7] Стековой автомат называется нестирающим, если он никогда не извлекается из стека. Класс языков, принимаемый недетерминированными, нестиранными стековыми автоматами, — это NSPACE ( n ²), который является расширенным набором контекстно-зависимых языков . ^[1] Класс языков, принимаемый детерминированными нестиранными стековыми автоматами, - это DSPACE ( n ⋅log( n )). ^[1]

Поочередно опускающиеся автоматы

Попеременный автомат с магазином (APDA) — это автомат с магазином с набором состояний.

$Q=Q_{\exists }\cup Q_{\forall }$ где $Q_{\exists }\cap Q_{\forall }=\emptyset$ .

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

Модель была представлена Чандрой , Козеном и Стокмейером . ^[8] Ладнер , Липтон и Стокмейер ^[9] доказал, что эта модель эквивалентна EXPTIME , т.е. язык принимается некоторым APDA тогда и только тогда , когда он может быть определен с помощью алгоритма экспоненциального времени.

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

См. также

Примечания

^ Набор битовых палиндромов четной длины не может быть распознан детерминированным КПК, но это контекстно-свободный язык с грамматикой S → ε | 0 С 0 | 1 С 1. ^[4]
^ Линейные ограниченные автоматы являются акцепторами класса контекстно-зависимых языков, ^[2]^: 225 который является собственным суперклассом контекстно-свободных языков и собственным подклассом распознаваемых по Тьюрингу (т.е. рекурсивно перечислимых ) языков. ^[2]^: 228

Ссылки

^ Jump up to: ^а ^б ^с Джон Э. Хопкрофт; Джеффри Д. Уллман (1967). «Нестирающие стек-автоматы» . Журнал компьютерных и системных наук . 1 (2): 166–186. дои : 10.1016/s0022-0000(67)80013-8 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Джон Э. Хопкрофт и Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Ридинг/Массачусетс: Аддисон-Уэсли. ISBN 0-201-02988-Х .
^ «Пушдаун-автоматы» . www.cs.odu.edu . Проверено 7 апреля 2024 г.
^ Джон Э. Хопкрофт; Раджив Мотвани; Джеффри Д. Уллман (2003). Введение в теорию автоматов, языки и вычисления . Эддисон Уэсли. Здесь: п.6.4.3, стр.249
^ Хольцер, Маркус; Кутриб, Мартин (2019). «Нерекурсивные компромиссы есть «почти везде» ». Вычисления с предвидением и промышленностью . 11558 : 25–36. дои : 10.1007/978-3-030-22996-2_3 . Это следует из цитируемой [22, предложение 7] и сформулированного наблюдения о том, что любой детерминированный автомат с выталкиванием может быть преобразован в эквивалентный конечный автомат ^{[ объяснить ]} не более чем двукратно экспоненциального размера.
^ Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Стековые автоматы и компиляция» . Дж. АКМ . 14 (1): 172–201. дои : 10.1145/321371.321385 .
^ Сеймур Гинзбург, Шейла А. Грейбах и Майкл А. Харрисон (1967). «Односторонний стек-автомат» . Дж. АКМ . 14 (2): 389–418. дои : 10.1145/321386.321403 .
^ Чандра, Ашок К.; Козен, Декстер К.; Стокмейер, Ларри Дж. (1981). «Чередование» . Журнал АКМ . 28 (1): 114–133. дои : 10.1145/322234.322243 . ISSN 0004-5411 .
^ Ладнер, Ричард Э.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (1984). «Попеременные автоматы с выталкиванием и стекированием». SIAM Journal по вычислительной технике . 13 (1): 135–155. дои : 10.1137/0213010 . ISSN 0097-5397 .
^ Айзиковиц, Тамар; Камински, Майкл (2011). «LR (0) Конъюнктивные грамматики и детерминированные синхронизированные автоматы с переменным нажатием». Информатика – теория и приложения . Конспекты лекций по информатике. Том. 6651. стр. 345–358. дои : 10.1007/978-3-642-20712-9_27 . ISBN 978-3-642-20711-2 . ISSN 0302-9743 .

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

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

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

[5] Набор битовых палиндромов четной длины не может быть распознан детерминированным КПК, но это контекстно-свободный язык с грамматикой S → ε | 0 С 0 | 1 С 1. ^[4]

[7] Линейные ограниченные автоматы являются акцепторами класса контекстно-зависимых языков, ^[2]^: 225 который является собственным суперклассом контекстно-свободных языков и собственным подклассом распознаваемых по Тьюрингу (т.е. рекурсивно перечислимых ) языков. ^[2]^: 228

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

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

[3] «Пушдаун-автоматы» . www.cs.odu.edu . Проверено 7 апреля 2024 г.

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

[6] Хольцер, Маркус; Кутриб, Мартин (2019). «Нерекурсивные компромиссы есть «почти везде» ». Вычисления с предвидением и промышленностью . 11558 : 25–36. дои : 10.1007/978-3-030-22996-2_3 . Это следует из цитируемой [22, предложение 7] и сформулированного наблюдения о том, что любой детерминированный автомат с выталкиванием может быть преобразован в эквивалентный конечный автомат ^{[ объяснить ]} не более чем двукратно экспоненциального размера.

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

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

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

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

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

[1]

[2]

[3]

[примечание 1]

[5]

[примечание 2]

[6]

[7]

[8]

[9]

[10]

[4]