Автомат с вложенным стеком

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

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

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

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

Автомат

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

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

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

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

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

и результаты

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

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

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

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

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

Пример

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

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

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

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

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

Примечания

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

Ссылки

^ Jump up to: ^а ^б Ахо, Альфред В. (июль 1969 г.). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .
^ Парти, Барбара ; Алиса тер Мейлен ; Роберт Э. Уолл (1990). Математические методы в лингвистике . Академическое издательство Клювер. стр. 536–542 . ISBN 978-90-277-2245-4 .
^ Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 0-201-02988-Х . Здесь: стр.390
^ Ахо (1969), стр.385 вверху
^ Бири, К. (июнь 1975 г.). «Автоматы с двусторонним вложенным стеком эквивалентны автоматам с двусторонним стеком» . Журнал компьютерных и системных наук . 10 (3): 317–339. дои : 10.1016/s0022-0000(75)80004-3 .
^ Шапиро, Роберт Гилман Майкл (4 декабря 1998 г.). О группах, словесная задача которых решается вложенным стековым автоматом (Технический отчет). arXiv : математика/9812028 . CiteSeerX 10.1.1.236.2029 . S2CID 12716492 .

[4] Первоначально Ахо использовал «$», «¢» и «#» вместо «[», «]» и « ] » соответственно. См. Ахо (1969), стр. 385 вверху.

[5] Juxataposition обозначает конкатенацию строк (наборов) и имеет более высокий приоритет привязки, чем объединение множеств ∪. Например, [Γ' обозначает набор всех строк длины 2, начинающихся с «[» и заканчивающихся символом из Γ'.

[7] Ахо изначально использовал левый и правый маркер стека, а именно. $ и ¢ в качестве правого и левого маркера ввода соответственно.

[8] Верхний символ (под)стека вместе с предшествующим ему левым конечным маркером «[» рассматривается как один символ.

[aho-1] Jump up to: ^а ^б Ахо, Альфред В. (июль 1969 г.). «Вложенные стековые автоматы» . Журнал АКМ . 16 (3): 383–406. дои : 10.1145/321526.321529 . S2CID 685569 .

[2] Парти, Барбара ; Алиса тер Мейлен ; Роберт Э. Уолл (1990). Математические методы в лингвистике . Академическое издательство Клювер. стр. 536–542 . ISBN 978-90-277-2245-4 .

[3] Джон Э. Хопкрофт, Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN 0-201-02988-Х . Здесь: стр.390

[6] Ахо (1969), стр.385 вверху

[9] Бири, К. (июнь 1975 г.). «Автоматы с двусторонним вложенным стеком эквивалентны автоматам с двусторонним стеком» . Журнал компьютерных и системных наук . 10 (3): 317–339. дои : 10.1016/s0022-0000(75)80004-3 .

[10] Шапиро, Роберт Гилман Майкл (4 декабря 1998 г.). О группах, словесная задача которых решается вложенным стековым автоматом (Технический отчет). arXiv : математика/9812028 . CiteSeerX 10.1.1.236.2029 . S2CID 12716492 .

[1]

[2]

[3]

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

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

[4]

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

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

[5]

[6]