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

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

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

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

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

Формальное определение [ править ]

Автомат [ править ]

А (недетерминирован двусторонний) вложенный стек автомата кортеж ⟨ 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 - множество конечных состояний.

Конфигурация [ править ]

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

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

Пример [ править ]

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

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

Свойства [ править ]

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

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

Заметки [ править ]

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

Ссылки [ править ]

^ a b Ахо, Альфред В. (июль 1969 г.). «Вложенные автоматы стека». Журнал 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). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X. Здесь: с.390
^ Ахо (1969), p.385 сверху
^ Бири, C. (июнь 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] Aho изначально использовал «$», «¢» и «#» вместо «[», «]» и « ] » соответственно. См. Ахо (1969), стр. 385 вверху.

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

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

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

[aho-1] Ахо, Альфред В. (июль 1969 г.). «Вложенные автоматы стека». Журнал 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). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X. Здесь: с.390

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

[9] Бири, C. (июнь 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 .

[1]