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

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

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

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

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

• 1 Формальное определение
  • 1.1 Автомат
  • 1.2 Конфигурация
  • 1.3 Пример
• 2 Свойства
• 3 Примечания
• 4 Ссылки

Автомат

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

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

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

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

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

и выводит

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

• q0∈ Q - начальное состояние,
• Z0∈ Γ - начальный символ стека,
• F ⊆ Q - набор конечных состояний.

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

A конфигурация или мгновенная описание такого автомата состоит из тройки ⟨q, [a 1a2... ai... a n-1 ], [Z 1X2... Xj... X m-1 ]⟩, где

• q ∈ Q - текущее состояние,
• [a1a2... ai... a n-1 ] - строка ввода; для удобства определены a 0 = [и n =]. Текущая позиция во входных данных, а именно. i, где 0 ≤ i ≤ n, отмечается подчеркиванием соответствующего символа.
• [Z1X2... Xj... X m-1 ]- стек, включая вложенные пакеты; для удобства определено X 1 = [Z 1 и X m= ]. Текущая позиция в стеке, а именно. j с 1 ≤ j ≤ m, отмечается подчеркиванием соответствующего символа.

Пример

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

Действие	Шаг	Стек
	1:	[a	b	[k	]	[p	]	c	]
создать подстек	2:	[a	b	[k	]	[p	[r	s	]	]	c	]
pop	3:	[a	b	[k	]	[p	[s	]	]	c	]
pop	4:	[a	b	[k	]	[p		]	c	]
уничтожить substack	5:	[a	b	[k	]	[p	]	c	]
сдвинуть вниз	6:	[a	b	[k	]	[p	]	c	]
сдвинуть вверх	7:	[a	b	[k	]	[p	]	c	]
сдвинуть вверх	8:	[a	b	[k	]	[p	]	c	]
push	9:	[a	b	[k	]	[n	o	p	]	c	]

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

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

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
4. ^Ахо (1969), стр.385 вверху
5. ^Бери, К. (июнь 1975). «Двусторонние вложенные стековые автоматы эквивалентны двусторонним стековым автоматам». Журнал компьютерных и системных наук. 10 (3): 317–339. doi : 10.1016 / s0022-0000 (75) 80004-3.
6. ^Шапиро, Роберт Гилман Майкл (4 декабря 1998 г.). О группах, проблема слов которых решается автоматом вложенного стека (Технический отчет). arXiv : math / 9812028. CiteSeerX 10.1.1.236.2029. S2CID 12716492.