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

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

Определение [ править ]

Стек деревьев [ править ]

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

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

Множество всех стеков деревьев над $Γ$ обозначается $TS(Γ)$ .

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

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

для любого $γ \in Γ$ .

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

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

для каждого натурального числа $n$ и любого $γ \in Γ$ .

Древовидные автоматы [ править ]

Древовидный стек-автомат представляет собой набор из 6 $A = (Q, Γ, Σ, q i, δ, Q f)$ , где

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

Конфигурация A $—$ это кортеж $(q, c, w)$ , где

$q$ — состояние ( текущее состояние ),
$c$ — стек дерева ( текущий стек дерева ), и
$w$ — слово над $Σ$ ( оставшееся слово, которое нужно прочитать).

Переход $τ = (q 1, u, p, f, q 2)$ применим , к конфигурации $(q, c, w)$ если

$q 1 = q$ ,
$p$ истинно для $c$ ,
$f$ определено для $c$ и
$u$ — префикс $w$ .

Отношение перехода $A$ — это бинарное отношение $⊢$ на конфигурациях $A$ , которое представляет собой объединение всех отношений $⊢ τ$ для перехода $τ = (q 1, u, p, f, q 2)$ , где всякий раз, когда $τ$ применимо к $(q, c, w)$ , мы имеем $(q, c, w) ⊢ τ (q 2, f (c), v)$ , а $v$ получается из $w$ удалением префикса $u$ .

Язык A $,$ — это набор всех слов $w$ для которых существует некоторое состояние $q \in Q f$ и некоторый стек деревьев $c$ такой, что $(q i, c i, w) ⊢ * (q, c, ε)$ где

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

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

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

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

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

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

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

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

^ Голубски, Вольфганг и Липпе, Вольфрам-М. (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] Набор строк является префиксно-замкнутым, если для каждого элемента $w$ в наборе все префиксы $w$ также присутствуют в наборе.

[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]

[б]

[1]