Автомат вложенного стека - Nested stack automaton

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

В теория автоматов, а автомат вложенного стека это конечный автомат который может использовать куча содержащие данные, которые могут быть дополнительными стеками.^[1] Как стековый автомат автомат с вложенным стеком может переходить вверх или вниз по стеку и читать текущий символ; кроме того, он может в любом месте создать новый стек, работать с ним, в конечном итоге уничтожить его и продолжить работу со старым стеком. Таким образом, стеки могут быть вложены рекурсивно на произвольную глубину; однако автомат всегда работает только с самым внутренним стеком.

Вложенный стековый автомат способен распознавать индексированный язык,^[2] и на самом деле класс индексированных языков - это в точности класс языков, принимаемых односторонним недетерминированный вложенные стековые автоматы.^[1]^[3]

Вложенные стековые автоматы не следует путать с встроенные выталкивающие автоматы, которые имеют меньшую вычислительную мощность.^{[нужна цитата ]}

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

Автомат

Автомат с вложенным стеком (недетерминированный двусторонний) - это кортеж ⟨Q, Σ, Γ, δ,q₀,Z₀,F,[,],]⟩ куда

Q, Σ, а Γ - непустое конечное множество состояний, входных символов и символов стека соответственно,
[, ], и ] - различные специальные символы, не содержащиеся в Σ ∪ Γ,
- [используется как левый указатель конца как для входной строки, так и для (под) строки стека,
- ] используется как маркер правого конца для этих строк,
- ] используется в качестве последнего маркера конца строки, обозначающего весь стек.^{[примечание 1]}
Расширенный входной алфавит определяется как Σ '= Σ ∪ {[,]}, расширенный стековый алфавит определяется как Γ' = Γ ∪ {]}, а множество входных направлений движения определяется как D = {-1,0,+1}.
δ, конечное управление, является отображением из Q × Σ '× (Γ' ∪ [Γ '∪ {], []}) на конечные подмножества Q × D × ([Γ^* ∪ D) такое, что δ отображает^{[заметка 2]}

Q × Σ '× [Γ	на подмножества Q × D × [Γ^*	(режим выталкивания),
Q × Σ '× Γ'	на подмножества Q × D × D	(режим чтения),
Q × Σ '× [Γ'	на подмножества Q × D × {+1}	(режим чтения),
Q × Σ '× {]}	на подмножества Q × D × {-1}	(режим чтения),
Q × Σ '× (Γ' ∪ [Γ ')	на подмножества Q × D × [Γ^*]	(режим создания стека) и
Q × Σ '× {[]}	на подмножества Q × D × {ε },	(режим разрушения стека),

Неформально верхний символ (под) стека вместе с предшествующим ему левым маркером конца "[" рассматривается как один символ;^[4] тогда δ читается как

текущее состояние,
текущий входной символ и
текущий символ стека,

и выходы

следующее состояние,
направление, в котором нужно двигаться на входе, и
направление, в котором следует двигаться по стеку, или строка символов для замены самого верхнего символа стека.

q₀ ∈ Q начальное состояние,
Z₀ ∈ Γ - начальный символ стека,
F ⊆ Q - множество конечных состояний.

Конфигурация

А конфигурация, или же мгновенное описание такого автомата состоит из тройки ⟨q,[а₁а₂...а_я...а_п-1], [Z₁Икс₂...Икс_j...Икс_м-1]⟩,куда

q ∈ Q текущее состояние,
[а₁а₂...а_я...а_п-1] - входная строка; для удобства, а₀ = [и а_п =] определяется^{[заметка 3]} Текущая позиция во входных данных, а именно. я с 0 ≤ я ≤ п, отмечен подчеркиванием соответствующего символа.
[Z₁Икс₂...Икс_j...Икс_м-1] - стек, включая подстаки; для удобства, Икс₁ = [Z₁ ^{[примечание 4]} и Икс_м = ] определено. Текущая позиция в стеке, а именно. j с 1 ≤ j ≤ м, отмечен подчеркиванием соответствующего символа.

Пример

Пример выполнения (строка ввода не показана):

Действие	Шаг	Куча
	1:	[а	б	[k	]	[п	]	c	]
создать подстак	2:	[а	б	[k	]	[п	[р	s	]	]	c	]
поп	3:	[а	б	[k	]	[п	[s	]	]	c	]
поп	4:	[а	б	[k	]	[п	[]	]	c	]
уничтожить субстак	5:	[а	б	[k	]	[п	]	c	]
двигаться вниз	6:	[а	б	[k	]	[п	]	c	]
двигаться вверх	7:	[а	б	[k	]	[п	]	c	]
двигаться вверх	8:	[а	б	[k	]	[п	]	c	]
толкать	9:	[а	б	[k	]	[п	о	п	]	c	]

Характеристики

Когда автоматам разрешено перечитывать вводимые данные ("двусторонние автоматы ") вложенные стеки не дают дополнительных возможностей распознавания языка по сравнению с простыми стеками.^[5]

Гилман и Шапиро использовали вложенные стековые автоматы для решения проблема со словом в определенных группы.^[6]

Примечания

^ Изначально Aho использовал «$», «¢» и «#» вместо «[», «]» и «]"соответственно. См. Ахо (1969), стр. 385 вверху.
^ Juxataposition означает строка (набор) конкатенация, и имеет более высокий приоритет привязки, чем set union ∪. Например, [Γ 'обозначает набор всех строк длины 2, начинающихся с «[» и заканчивающихся символом из Γ'.
^ Изначально Aho использовал левый и правый маркер стека, а именно. $ и ¢, как правый и левый маркер ввода, соответственно.
^ Верхний символ (под) стека вместе с предшествующим ему левым маркером конца «[» рассматривается как один символ.