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

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

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

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

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

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