# Autòmat amb pila d'arbre

En teoria d'autòmats, un autòmat amb pila d'arbre és un autòmat amb la capacitat de manipular una pila amb forma d'arbre. És un autòmat amb emmagatzemament on el seu element d'emmagatzematge s'assembla al de l'autòmat per subprocessos. Aquest tipus d'autòmats reconeixen els llenguatges generats per múltiples gramàtiques lliures de context o llenguatges lineals de reescriptura lliure de context.

## Definició
### Pila amb arbre

Per un conjunt finit i no buit $\Gamma$', una pila sobre $\Gamma$ és una tubla $\langle t,p\rangle$ on:
* t és una funció parcial de cadenes d'enters positius cap al conjunt $\Gamma \cup$@ amb un domini de prefix tancat (anomenat arbre)
* @ (anomenat símbol del fons) no és a $\Gamma$ i apareix a l'arrel de t
* p és un element del domini de t (anomenat punter de la pila)
El conjunt de totes les piles amb arbres sobre $\Gamma$ s'anomena$TS(\Gamma )$
El conjunt de predicats sobre $TS(\Gamma )$', denotats per $Pred(\Gamma )$', conté els següents predicats unaris:
* true que és veritat per qualsevol pila sobre $\Gamma$
* bottom que és veritat per una pila el punter de la qual estigui apuntant al símbol de fons
* $equals(\gamma )$ que és veritat per alguna pila $\langle t,p\rangle$ si $t(p)=\gamma$
per tot $\gamma \in \Gamma$.
El conjunt d'instruccions a $TS(\Gamma )$, denotades com $Instr(\Gamma )$, contenen les següents funcions parcials:
* id: $TS(\Gamma )\to TS(\Gamma )$ que és la funció identitat a $TS(\Gamma )$
* push$_{n,γ}$ : $TS(\Gamma )\to TS(\Gamma )$que donat una pila amb arbre $\langle t,p\rangle$afegeix un parell $(pn\mapsto \gamma )$a l'arbre t i posa el punter de la pila a pn (és a dir, afegeix $\gamma$al fill número n) si pn no està dins el domini de t.
* up$_n$ :$TS(\Gamma )\to TS(\Gamma )$reemplaça el punter actual p per pn (mou el punter de la pila cap al fill número n) si pn està al domini de t.
* $_{down}$ :$TS(\Gamma )\to TS(\Gamma )$treu l'últim símbol on apunta el punter de la pila (mou el punter al pare de la posició actual)
* set$_γ$ :$TS(\Gamma )\to TS(\Gamma )$reemplaça el símbol sota el punter per $\gamma$
per qualsevol enter positiu n i tot $\gamma \in \Gamma$
| Exemple d'instrucció id | Exemple d'instrucció push | Exemple d'instruccions up i down | Exemple d'instrucció set |

### Autòmat amb pila d'arbre

Un autòmat amb pila d'arbre és una 6-tupla A = (Q, Γ, Σ, q$_i$, δ, Q$_f$) on:
* Q, Γ, i Σ son conjunts finits (estat, símbols de la pila i símbols d'entrada)
* q$_i$ ∈ Q és l'estat inicial,
* δ ⊆$_{fin.}$ Q × (Σ ∪ {ε}) × Pred(Γ) × Instr(Γ) × Q anomenats transicions, i
* Q$_f$ ⊆ TS(Γ) anomenats estats finals.
Una configuració d'A és una tupla (q, c, w) on:
* q és un estat (l'estat actual),
* c és una pila amb arbre
* w és una paraula sobre Σ
Una transició τ = (q$_1$, u, p, f, q₂) és aplicable a una configuració (q, c, w) si
* q$_1$ = q,
* p és cert a c,
* f es definida per c, i
* u és un prefix de w.
La relació de transició d'A és la relació binària ⊢ de configuracions d'A que és la unió de totes les relacions ⊢$_τ$ per una transició τ = (q$_1$, u, p, f, q₂) on, per tot τ és aplicable a (q, c, w), es te (q, c, w) ⊢$_τ$ (q₂, f(c), v) i v s'obté de w eliminant-hi el prefix u.
El llenguatge d'A és el conjunt de totes les paraules w per les quals algun estat q ∈ Q$_f$ i alguna pila amb arbre c tal que (q$_i$, c$_i$, w) ⊢$^*$ (q, c, ε) on
* ⊢$^*$ és la clausura reflexiva transitiva de ⊢ i
* c$_i$ = (t$_i$, ε) tal que t$_i$ assigna el símbol @ a ε i no està definit per altres casos.

## Formalismes relacionats

Aquesta mena de màquines son equivalents a les Màquines de Turing.
Un autòmat amb pila d'arbre s'anomena restringit-k per algun nombre positiu k si durant qualsevol moment de l'execució de l'autòmat, qualsevol posició de la pila d'arbre s'hi accedeix com a màxim k cops.
Un autòmat restringit-1 és equivalent a un autòmat a pila i, per tant, també és equivalent a les gramàtiques lliures de context. Un autòmat restringit-k és equivalent a una gramàtica de sistema lineal de rescriptura lliure de context i a múltiples gramàtiques lliures de context de sortida com a molt k.

## Referències

* ↑ Golubski, Wolfgang; Lippe, Wolfram-M. «Tree-stack automata» (en anglès). Proceedings of the 15th Symposium on Mathematical Foundations of Computer Science (MFCS 1990). Springer Berlin Heidelberg, 1990, pàg. 313–321. DOI: 10.1007/bfb0029624.
* ↑ Scott, Dana «Some definitional suggestions for automata theory». Journal of Computer and System Sciences, 1, 2, 01-08-1967, pàg. 187–212. DOI: 10.1016/S0022-0000(67)80014-X. ISSN: 0022-0000.
* 1 2 Denkinger, Tobias «An Automata Characterisation for Multiple Context-Free Languages» (en anglès). Proceedings of the 20th International Conference on Developments in Language Theory (DLT 2016). Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2016, pàg. 138–150. DOI: 10.1007/978-3-662-53132-7_12.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :