Автомат стека деревьев - Tree stack automaton

Автомат стека дерева^[а] (множественное число: автоматы стека деревьев) формализм рассматривается в теория автоматов. Это конечный автомат с дополнительной возможностью манипулировать дерево -образный стек. Это автомат с хранилищем^[2] чье хранилище примерно напоминает конфигурацию ниточный автомат. Ограниченный класс автоматов стека деревьев распознает точно языки генерируется множеством контекстно-свободные грамматики^[3] (или линейные системы перезаписи без контекста ).

Определение

Стек дерева

Стек дерева с указателем стека 1.2 и доменом {ε, 1, 42, 1.2, 1.5, 1.5.3}

Для конечного и непустого множества $Γ$ , а дерево над $Γ$ кортеж $(т, п)$ где

$т$ это частичная функция из строк положительных чисел в набор $Γ \cup {@$ } с приставка -закрыто^[b] домен (называется дерево),
$@$ (называется нижний символ) не в $Γ$ и появляется точно в корне $т$ , и
$п$ является элементом области $т$ (называется указатель стека).

Набор всех деревьев складывается поверх $Γ$ обозначается $TS (Γ)$ .

Набор предикаты на $TS (Γ)$ , обозначаемый $Пред (Γ)$ , содержит следующие унарный предикаты:

$правда$ что верно для любого стека деревьев над $Γ$ ,
$дно$ что верно для стеков деревьев, указатель стека которых указывает на нижний символ, и
$равно (γ)$ что верно для некоторого стека деревьев $(т, п)$ если $т (п) = γ$ ,

для каждого $γ \in Γ$ .

Набор инструкции на $TS (Γ)$ , обозначаемый $Instr (Γ)$ , содержит следующие частичные функции:

$id: TS (Γ) \to TS (Γ)$ которая является тождественной функцией на $TS (Γ)$ ,
$От себя п, γ : TS (Γ) \to TS (Γ)$ который добавляет для данного стека дерева $(т, п)$ пара $(пн \mapsto γ)$ к дереву $т$ и устанавливает указатель стека на $пн$ (т.е. толкает $γ$ к $п$ -я дочерняя позиция), если $пн$ еще не в сфере $т$ ,
$вверх п : TS (Γ) \to TS (Γ)$ который заменяет текущий указатель стека $п$ к $пн$ (т.е. перемещает указатель стека на $п$ -я дочерняя позиция), если $пн$ находится в сфере $т$ ,
$вниз: TS (Γ) \to TS (Γ)$ который удаляет последний символ из указателя стека (т.е. перемещает указатель стека в родительскую позицию) и
$набор γ : TS (Γ) \to TS (Γ)$ который заменяет символ, находящийся в данный момент под указателем стека, на $γ$ ,

для каждого положительного целого числа $п$ и каждый $γ \in Γ$ .

Иллюстрация идентификатора инструкции в стеке дерева

Иллюстрация инструкции push на стеке дерева

Иллюстрация инструкций вверх и вниз на стеке дерева

Иллюстрация набора инструкций на стеке дерева

Автоматы стека деревьев

А автомат стека деревьев представляет собой набор из шести $А = (Q, Γ, Σ, q я, δ, Q ж)$ где

$Q$ , $Γ$ , и $Σ$ - конечные множества (элементы которых называются состояния, символы стека, и входные символысоответственно),
$q я \in Q$ (в начальное состояние),
$δ \subseteq плавник. Q \times (Σ \cup {ε}) \times Pred (Γ) \times Instr (Γ) \times Q$ (элементы которого называются переходы), и
$Q ж \subseteq TS (Γ)$ (элементы которого называются конечные состояния).

А конфигурация $А$ кортеж $(q, c, ш)$ где

$q$ это государство ( Текущее состояние),
$c$ это стек дерева ( текущий стек дерева), и
$ш$ это слово закончилось $Σ$ (в оставшееся слово читать).

Переход $τ = (q 1, ты, п, ж, q 2)$ является применимый к конфигурации $(q, c, ш)$ если

$q 1 = q$ ,
$п$ верно на $c$ ,
$ж$ определяется для $c$ , и
$ты$ является префиксом $ш$ .

В переходное отношение $А$ это бинарное отношение $⊢$ по конфигурации $А$ это союз всех отношений $⊢ τ$ для перехода $τ = (q 1, ты, п, ж, q 2)$ где, когда $τ$ применимо к $(q, c, ш)$ , у нас есть $(q, c, ш) ⊢ τ (q 2, ж (c), v)$ и $v$ получается из $ш$ убрав префикс $ты$ .

В язык $А$ это набор всех слов $ш$ для которого есть какое-то состояние $q \in Q ж$ и немного дерева $c$ такой, что $(q я, c я, w) ⊢ * (q, c, ε)$ где

$⊢ *$ это рефлексивное переходное замыкание из $⊢$ и
$c я = (т я, ε)$ такой, что $т я$ назначает для $ε$ символ $@$ и не определен в противном случае.

Связанные формализмы

Автоматы стека деревьев эквивалентны Машины Тьюринга.

Автомат стека дерева называется $k$ -ограниченный для некоторого положительного натурального числа $k$ если во время любого запуска автомата доступ к любой позиции стека дерева осуществляется не более чем $k$ раз снизу.

1-ограниченные автоматы стека деревьев эквивалентны выталкивающие автоматы и поэтому также контекстно-свободные грамматики. $k$ -ограниченные автоматы стека деревьев эквивалентны линейные системы перезаписи без контекста и несколько контекстно-свободных грамматик разветвления не более $k$ (для каждого положительного целого числа $k$ ).^[3]

Примечания

^ не путать с устройством с таким же названием, представленным в 1990 году Вольфгангом Голубски и Вольфрамом-М. Липпе ^[1]
^ Набор струн закрытый по префиксу если для каждого элемента $ш$ в наборе все префиксы $ш$ тоже есть в комплекте.

использованная литература

^ Голубски, Вольфганг и Липпе, Вольфрам-М. (1990). Древовидные автоматы. Труды 15-го симпозиума по математическим основам информатики (MFCS 1990). Конспект лекций по информатике, Vol. 452, страницы 313–321, DOI: 10.1007 / BFb0029624.
^ Скотт, Дана (1967). Некоторые предложения по определению теории автоматов. Журнал компьютерных и системных наук, Vol. 1 (2), страницы 187–212, DOI: 10.1016 / s0022-0000 (67) 80014-x.
^ ^а ^б Денкингер, Тобиас (2016). Автоматическая характеристика для нескольких контекстно-свободных языков. Материалы 20-й Международной конференции по развитию теории языка (DLT 2016). Конспект лекций по информатике, Vol. 9840, страницы 138–150, DOI: 10.1007 / 978-3-662-53132-7_12.

[2] не путать с устройством с таким же названием, представленным в 1990 году Вольфгангом Голубски и Вольфрамом-М. Липпе ^[1]

[5] Набор струн закрытый по префиксу если для каждого элемента $ш$ в наборе все префиксы $ш$ тоже есть в комплекте.

[GolLip90-1] Голубски, Вольфганг и Липпе, Вольфрам-М. (1990). Древовидные автоматы. Труды 15-го симпозиума по математическим основам информатики (MFCS 1990). Конспект лекций по информатике, Vol. 452, страницы 313–321, DOI: 10.1007 / BFb0029624.

[Sco67-3] Скотт, Дана (1967). Некоторые предложения по определению теории автоматов. Журнал компьютерных и системных наук, Vol. 1 (2), страницы 187–212, DOI: 10.1016 / s0022-0000 (67) 80014-x.

[Den16-4] а ^б Денкингер, Тобиас (2016). Автоматическая характеристика для нескольких контекстно-свободных языков. Материалы 20-й Международной конференции по развитию теории языка (DLT 2016). Конспект лекций по информатике, Vol. 9840, страницы 138–150, DOI: 10.1007 / 978-3-662-53132-7_12.

[а]

[2]

[3]

[b]

[1]