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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle M = (Q, сигма, гамма, дельта, q_ {0}, Z, F)}$ куда

${displaystyle Q}$ конечный набор состояния
${displaystyle Sigma}$ конечное множество, которое называется вводить алфавит
${displaystyle Gamma}$ конечное множество, которое называется сложить алфавит
${displaystyle delta}$ конечное подмножество ${displaystyle Q imes (Sigma cup {varepsilon}) imes Gamma imes Q imes Gamma ^ {*}}$ , то переходное отношение
${displaystyle q_ {0} в Q}$ это начальное состояние
${displaystyle Zin Gamma}$ это начальный символ стека
${displaystyle Fsubseteq Q}$ это набор принимающие государства

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

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

${displaystyle delta}$ это функция перехода, отображение ${displaystyle Q imes (Sigma cup {varepsilon}) imes Gamma}$ на конечные подмножества ${displaystyle Q imes 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)}) в дельте}$ . Обратите внимание, что конечный в этом определение существенно.

Расчеты

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

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

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

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

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

${displaystyle L (M) = {win Sigma ^ {*} | (q_ {0}, w, Z) vdash _ {M} ^ {*} (f, varepsilon, gamma)}$ с ${displaystyle fin F}$ и ${displaystyle gamma in Gamma ^ {*}}}$ (конечное состояние)
${displaystyle N (M) = {win Sigma ^ {*} | (q_ {0}, w, Z) vdash _ {M} ^ {*} (q, varepsilon, varepsilon)}$ с ${displaystyle qin 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 ngeq 0}}$ по конечному состоянию:

КПК для

{displaystyle {0 ^ {n} 1 ^ {n} mid ngeq 0}}

(по конечному состоянию)

${displaystyle M = (Q, сигма, гамма, дельта, 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)}

.

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

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

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

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

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

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

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

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

Входная строка = 0011. Существуют различные вычисления, в зависимости от момента перехода из состояния. п заявить 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, эпсилон, 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 (г, 1, Z)}$
  Конечным состоянием является принятие, но ввод не принимается таким образом, поскольку он не был (полностью) прочитан.

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

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

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

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

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

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

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

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

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

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

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

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

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

{displaystyle M = (Q, сигма, гамма, дельта, q_ {0}, F)}

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

{displaystyle, delta}

:

{displaystyle Q imes Sigma _ {epsilon} imes Gamma ^ {*} longrightarrow P (Q imes Gamma ^ {*})}

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

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

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

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

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

куда ${displaystyle q_ {1}, q_ {2} в Q, выиграть Sigma _ {epsilon}, x_ {1}, x_ {2}, ldots, x_ {m} in Gamma ^ {*}, mgeq 0, y_ {1 }, y_ {2}, ldots, y_ {n} в гамме ^ {*}, ngeq 0}$ .

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

{displaystyle {egin {array} {lcl} delta ^ {'} (q_ {1}, w, x_ {1}) & longrightarrow & (p_ {1}, epsilon) delta ^ {'} (p_ {1}, эпсилон, x_ {2}) & длинная правая стрелка & (p_ {2}, эпсилон) & vdots & delta ^ {'} (p_ {m-1}, эпсилон, x_ {m}) & длинная правая стрелка & (p_ {m}, эпсилон ) 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}) конец {массив}}}

Стек автомат

В качестве обобщения автоматов выталкивания вниз Гинзбург, Грейбах и Харрисон (1967) исследовали стековые автоматы, который может дополнительно перемещаться влево или вправо во входной строке (окруженный специальными символами конечных маркеров для предотвращения выскальзывания) и перемещаться вверх или вниз по стеку в режиме только для чтения.^[4]^[5] Стек-автомат называется не стирающий если он никогда не выскакивает из стека. Класс языков, принимаемых недетерминированными, нестирающими стековыми автоматами, является NSPACE (п²), который является надмножеством контекстно-зависимые языки.^[1] Класс языков, приемлемых для детерминированных нестирающихся стековых автоматов, равен DSPACE (п⋅log (п)).^[1]

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

An автомат попеременного опускания (APDA) - автомат выталкивания с набором состояний

${displaystyle Q = Q_ {exists} чашка Q_ {forall}}$ куда ${displaystyle Q_ {exists} cap Q_ {forall} = emptyset}$ .

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

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

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

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

Примечания

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

внешняя ссылка

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

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

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

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

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

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

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

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

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

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

[AizikowitzKaminski2011-10] Айзиковиц, Тамар; Камински, Майкл (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]

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

[заметка 2]

[4]

[5]

[6]

[7]

[8]

[3]