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

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

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

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

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

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

Неофициальное описание [ править ]

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

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

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

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

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

Если в каждой ситуации возможно не более одного такого переходного действия, то автомат называется детерминированным автоматом выталкивания (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\subseteq Q}$это набор принимающих состояний

Элемент - это переход . Он имеет предполагаемое значение, что в состоянии , на входе и с самым верхним символом стека, он может читать , изменять состояние на , выталкивать, заменяя его нажатием . Компонент переходного соотношения используется для формализации , что КПК может либо прочитать письмо от входа, или перейти оставляя вход нетронутым. ^{[ необходима цитата ]}${\displaystyle (p,a,A,q,\alpha )\in \delta }$${\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 \cup \{\varepsilon \})}$

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

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

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

Расчеты

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

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

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

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

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

1. ${\displaystyle L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )}$с и (конечное состояние)${\displaystyle f\in F}$${\displaystyle \gamma \in \Gamma ^{*}\}}$
2. ${\displaystyle N(M)=\{w\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(M)=N(M')}$${\displaystyle M}$${\displaystyle M'}$${\displaystyle N(M)=L(M')}$

Пример [ править ]

Ниже приводится формальное описание КПК, распознающего язык по конечному состоянию:${\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=\{r\}}$

Отношение перехода состоит из следующих шести инструкций:${\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 (p,a,A,q,\alpha )}$${\displaystyle a;A/\alpha }$${\displaystyle \alpha }$

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

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

КПК и контекстно-свободные языки [ править ]

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

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

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

КПК принимает пустой стек. Его начальный символ стека - это начальный символ грамматики. ^{[ необходима цитата ]}

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

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

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

Язык строк, принимаемый детерминированным автоматом выталкивания, называется детерминированным контекстно-свободным языком . Не все контекстно-свободные языки детерминированы. ^{[примечание 1]} Как следствие, DPDA является строго более слабым вариантом КПК, и не существует алгоритма преобразования КПК в эквивалентный DPDA, если такой DPDA существует. ^{[ необходима цитата ]}

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

КПК и машины Тьюринга [ править ]

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

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

Универсальный автомат выталкивания (GPDA) [ править ]

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

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

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

Автоматические чередующиеся выталкиватели [ редактировать ]

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

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

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

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

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

См. Также [ править ]

• Штабелеукладчик
• Бесконтекстная грамматика
• Конечный автомат
• Счетчик автомат
• Автомат очереди

Примечания [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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