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

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

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

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

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

Автомат

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

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

Q × Σ' × [Г	на подмножества Q × D × [Γ ^*	(режим pushdown),
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 , [ a ₁a ₂ ... a _i ... a _n_-1 ] , [ Z ₁X ₂ ... X _j ... X _m_-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, начинающихся с "[" и заканчивающихся символом из Γ'.
^ Первоначально Aho использовал левый и правый маркеры стека, а именно $ и ¢, в качестве правого и левого маркера ввода соответственно.
^ Верхний символ (под)стека вместе с предшествующим ему левым конечным маркером «[» рассматривается как один символ.

Ссылки

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

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

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

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

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

[aho-1] Aho, Alfred V. (июль 1969). "Nested Stack Automata". Журнал ACM . 16 (3): 383– 406. doi : 10.1145/321526.321529 . S2CID 685569.

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

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

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

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

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