Раскрывающийся автомат

редактировать

Классы автоматов (Щелчок по каждому слою дает статью по этой теме)

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

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

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

Содержание

1 Неформальное описание
2 Формальное определение
3 Пример
4 Понимание процесса вычислений
5 КПК и контекстно-свободные языки
6 Обобщенный автомат выталкивания (GPDA)
7 Стековый автомат
8 Чередующиеся автоматические выталкивающие устройства
9 См. Также
10 Примечания
11 Ссылки
12 Внешние ссылки

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

Схема автомата выталкивания вниз

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

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

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

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

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

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

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

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

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

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

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

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

$δ {\ displaystyle \ delta}$ $\ delta$ - функция перехода, отображение $Q × (Σ ∪ {ε}) × Γ {\ displaystyle Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma}$ ${\ displaystyle Q \ times (\ Sigma \ cup \ {\ varepsilon \}) \ times \ Gamma}$ в конечное подмножества $Q × Γ ∗ {\ displaystyle Q \ times \ Gamma ^ {*}}$ $Q \ times \ Gamma ^ {*}$

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

Вычисления

шаг автомата выталкивания

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

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

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

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

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

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

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

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

Пример

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

КПК для

{0 n 1 n ∣ n ≥ 0} { \ Displaystyle \ {0 ^ {n} 1 ^ {n} \ mid n \ geq 0 \}}

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

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

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

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

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

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

(p, 0, Z, p, AZ)

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

(p, 0, A, p, AA)

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

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

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

(p, \ эпсилон, A, q, A)

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

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

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

(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, α) {\ displaystyle (p, a, A, q, \ alpha)}$ $(p, a, A, q, \ alpha)$ ребром из состояния p в состояние q помечено $a; A / α {\ displaystyle a; A / \ alpha}$ $a; A / \ альфа$ (читать a; заменить A на $α {\ displaystyle \ alpha}$ $\ alpha$ ).

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

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

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

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

КПК и контекстно-свободный languages

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

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

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

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

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

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

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

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

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

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

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

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

M = (Q, Σ, Γ, δ, q 0, F) {\ displaystyle M = (Q, \ \ Sigma, \ \ Гамма, \ \ дельта, \ q_ {0}, \ F)}

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

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

δ {\ displaystyle \, \ delta}

\, \ delta

Q × Σ ϵ × Γ ∗ ⟶ P (Q × Γ ∗) {\ displaystyle Q \ times \ Sigma _ {\ epsilon} \ times \ Gamma ^ {* } \ longrightarrow P (Q \ times \ Gamma ^ {*})}

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

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

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

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

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

Пусть $δ (q 1, w, x 1 x 2 ⋅ xm) ⟶ ( q 2, y 1 y 2... yn) {\ displaystyle \ delta (q_ {1}, w, x_ {1} x_ {2} \ cdot x_ {m}) \ longrightarrow (q_ {2}, y_ { 1} y_ {2}... y_ {n})}$ ${\ displaystyle \ 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 ∈ Q, w ∈ Σ ϵ, Икс 1, Икс 2,…, xm ∈ Γ ∗, m ≥ 0, y 1, y 2,…, yn ∈ Γ ∗, n ≥ 0 {\ 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 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}$ .

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

δ ′ (q 1, w, x 1) ⟶ (p 1, ϵ) δ ′ (p 1, ϵ, x 2) ⟶ (p 2, ϵ) ⋮ δ ′ (pm - 1, ϵ, xm) ⟶ (pm, ϵ) δ ′ (pm, ϵ, ϵ) ⟶ (pm + 1, yn) δ ′ (pm + 1, ϵ, ϵ) ⟶ (pm + 2, yn - 1) ⋮ δ ′ (pm + n - 1, ϵ, ϵ) ⟶ (q 2, y 1) {\ displaystyle {\ begin {array} {lcl} \ delta ^ {'} (q_ {1}, w, x_ {1}) \ longrightarrow (p_ {1}, \ ep силон) \\\ 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}}}

{\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) - автомат выталкивания с набором состояний

$Q = Q ∃ ∪ Q ∀ {\ displaystyle Q = Q _ {\ exists} \ cup Q _ {\ forall}}$ ${\ displaystyle Q = Q _ {\ exists} \ cup Q _ {\ forall}}$ где $Q ∃ ∩ Q ∀ = ∅ {\ displaystyle Q _ {\ exists} \ cap Q _ {\ forall} = \ emptyset}$ ${\ displaystyle Q _ {\ exists} \ cap Q _ {\ forall} = \ emptyset}$ .

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

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

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

См. Также

Примечания

Ссылки

^ Джон Э. Хопкрофт; Джеффри Д. Ульман (1967). «Неизменные стековые автоматы». Журнал компьютерных и системных наук. 1 (2): 166–186. doi : 10.1016 / s0022-0000 (67) 80013-8.
^ Джон Э. Хопкрофт и Джеффри Д. Уллман (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.
^Chandra, Ashok K.; Kozen, Dexter C.; Стокмейер, Ларри Дж. (1981). «Чередование». Журнал ACM. 28 (1): 114–133. doi : 10.1145 / 322234.322243. ISSN 0004-5411.
^Ladner, Richard E.; Липтон, Ричард Дж.; Стокмейер, Ларри Дж. (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)