Automat zásobníku stromů - Tree stack automaton

Automat zásobníku stromů^[A] (množné číslo: automaty zásobníku stromů) je a formalismus uvažováno v teorie automatů. Je to konečný stavový automat s další schopností manipulovat a strom -tvarovaná zásobník. Je to automat s úložištěm^[2] jehož úložiště zhruba připomíná konfigurace a automat závitů. Omezená třída automatů zásobníku stromů přesně rozpozná jazyky generováno více bezkontextové gramatiky^[3] (nebo lineární bezkontextové přepisovací systémy ).

Definice

Stoh stromů

Zásobník stromů s ukazatelem zásobníku 1.2 a doménou {ε, 1, 42, 1.2, 1.5, 1.5.3}

Pro konečnou a neprázdnou množinu $Γ$ , a zásobník stromů přes $Γ$ je n-tice $(t, str)$ kde

$t$ je částečná funkce od řetězců kladných celých čísel po množinu $Γ \cup {@$ } s předpona -Zavřeno^[b] doména (volala strom),
$@$ (volala dolní symbol) není v $Γ$ a objeví se přesně v kořenovém adresáři $t$ , a
$str$ je prvek domény $t$ (volala ukazatel zásobníku).

Sada všech stromů se hromadí $Γ$ je označen $TS (Γ)$ .

Sada predikáty na $TS (Γ)$ , označeno $Před (Γ)$ , obsahuje následující unární predikáty:

$skutečný$ což platí pro jakýkoli zásobník stromů $Γ$ ,
$dno$ což platí pro hromádky stromů, jejichž ukazatel zásobníku ukazuje na dolní symbol, a
$rovná se(y)$ což platí pro nějaký stromový stack $(t, str)$ -li $t (str) = y$ ,

pro každého $y \in Γ$ .

Sada instrukce na $TS (Γ)$ , označeno $Instr (Γ)$ , obsahuje následující dílčí funkce:

$id: TS (Γ) \to TS (Γ)$ na kterém je funkce identity $TS (Γ)$ ,
$tlačit n, y : TS (Γ) \to TS (Γ)$ který přidává pro daný stromový zásobník $(t, str)$ pár $(pn \mapsto y)$ ke stromu $t$ a nastaví ukazatel zásobníku na $pn$ (tj. tlačí $y$ do $n$ -té dítě pozice) pokud $pn$ dosud není doménou domény $t$ ,
$nahoru n : TS (Γ) \to TS (Γ)$ který nahradí aktuální ukazatel zásobníku $str$ podle $pn$ (tj. přesune ukazatel zásobníku na $n$ -té dítě pozice) pokud $pn$ je v doméně $t$ ,
$dolů: TS (Γ) \to TS (Γ)$ který odstraní poslední symbol z ukazatele zásobníku (tj. přesune ukazatel zásobníku na nadřazenou pozici) a
$soubor y : TS (Γ) \to TS (Γ)$ který nahradí symbol aktuálně pod ukazatelem zásobníku za $y$ ,

pro každé kladné celé číslo $n$ a každý $y \in Γ$ .

Ilustrace ID instrukce na zásobníku stromu

Ilustrace instrukce push na stromě

Ilustrace pokynů nahoru a dolů na hromádce stromů

Ilustrace instrukční sady na zásobníku stromů

Stromové automaty

A automat zásobníku stromů je n-tice $A = (Q, Γ, Σ, q i, δ, Q F)$ kde

$Q$ , $Γ$ , a $Σ$ jsou konečné množiny (jejichž prvky se nazývají státy, symboly zásobníku, a vstupní symboly, v uvedeném pořadí),
$q i \in Q$ (dále jen počáteční stav),
$δ \subseteq ploutev. Q \times (Σ \cup {ε}) \times Před (Γ) \times Instr (Γ) \times Q$ (jehož prvky se nazývají přechody), a
$Q F \subseteq TS (Γ)$ (jehož prvky se nazývají konečné stavy).

A konfigurace $A$ je n-tice $(q, C, w)$ kde

$q$ je stát ( aktuální stav),
$C$ je zásobník stromů ( aktuální zásobník stromů), a
$w$ je slovo $Σ$ (dále jen zbývající slovo ke čtení).

Přechod $τ = (q 1, u, str, F, q 2)$ je použitelný do konfigurace $(q, C, w)$ -li

$q 1 = q$ ,
$str$ je pravda na $C$ ,
$F$ je definováno pro $C$ , a
$u$ je předpona $w$ .

The přechodový vztah $A$ je binární relace $⊢$ o konfiguracích $A$ to je spojení všech vztahů $⊢ τ$ pro přechod $τ = (q 1, u, str, F, q 2)$ kde kdykoli $τ$ platí pro $(q, C, w)$ , my máme $(q, C, w) ⊢ τ (q 2, F (C), proti)$ a $proti$ se získává z $w$ odstraněním předpony $u$ .

The jazyk $A$ je množina všech slov $w$ pro které existuje nějaký stát $q \in Q F$ a nějaký stromový stoh $C$ takhle $(q i, C i, w) ⊢ * (q, C, ε)$ kde

$⊢ *$ je reflexní přechodné uzavření z $⊢$ a
$C i = (t i, ε)$ takhle $t i$ přiřazuje pro $ε$ symbol $@$ a není definováno jinak.

Související formalizmy

Stromové automaty jsou ekvivalentní Turingovy stroje.

Volá se automat zásobníku stromů $k$ -omezený pro nějaké kladné přirozené číslo $k$ pokud během libovolného běhu automatu je přístupná maximálně libovolná poloha zásobníku stromů $k$ krát zdola.

1-omezené automaty zásobníku stromů jsou ekvivalentní pushdown automaty a proto také bezkontextové gramatiky. $k$ -omezené automaty zásobníku stromů jsou ekvivalentní lineární bezkontextové přepisovací systémy a nanejvýš několik bezkontextových gramatik fan-out $k$ (pro každé kladné celé číslo $k$ ).^[3]

Poznámky

^ nezaměňovat se zařízením se stejným názvem, které v roce 1990 zavedli Wolfgang Golubski a Wolfram-M. Lippe ^[1]
^ Sada řetězců je předpona uzavřena pokud pro každý prvek $w$ v sadě všechny předpony $w$ jsou také v sadě.

Reference

^ Golubski, Wolfgang a Lippe, Wolfram-M. (1990). Stromové automaty. Sborník z 15. symposia o matematických základech informatiky (MFCS 1990). Lecture Notes in Computer Science, Vol. 452, strany 313–321, doi: 10,1007 / BFb0029624.
^ Scott, Dana (1967). Několik definičních návrhů pro teorii automatů. Journal of Computer and System Sciences, sv. 1 (2), strany 187–212, doi: 10,1016 / s0022-0000 (67) 80014-x.
^ ^A ^b Denkinger, Tobias (2016). Charakterizace automatů pro více jazyků bez kontextu. Sborník příspěvků z 20. mezinárodní konference o vývoji v teorii jazyků (DLT 2016). Lecture Notes in Computer Science, Vol. 9840, strany 138–150, doi: 10.1007 / 978-3-662-53132-7_12.

[2] zaměňovat se zařízením se stejným názvem, které v roce 1990 zavedli Wolfgang Golubski a Wolfram-M. Lippe ^[1]

[5] Sada řetězců je předpona uzavřena pokud pro každý prvek $w$ v sadě všechny předpony $w$ jsou také v sadě.

[GolLip90-1] Golubski, Wolfgang a Lippe, Wolfram-M. (1990). Stromové automaty. Sborník z 15. symposia o matematických základech informatiky (MFCS 1990). Lecture Notes in Computer Science, Vol. 452, strany 313–321, doi: 10,1007 / BFb0029624.

[Sco67-3] Scott, Dana (1967). Několik definičních návrhů pro teorii automatů. Journal of Computer and System Sciences, sv. 1 (2), strany 187–212, doi: 10,1016 / s0022-0000 (67) 80014-x.

[Den16-4] A ^b Denkinger, Tobias (2016). Charakterizace automatů pro více jazyků bez kontextu. Sborník příspěvků z 20. mezinárodní konference o vývoji v teorii jazyků (DLT 2016). Lecture Notes in Computer Science, Vol. 9840, strany 138–150, doi: 10.1007 / 978-3-662-53132-7_12.

[A]

[2]

[3]

[b]

[1]