Per un conjunt finit i no buit , una pila sobre és una tubla on:
t és una funció parcial de cadenes d'enters positius cap al conjunt @ amb un domini de prefix tancat (anomenat arbre)
@ (anomenat símbol del fons) no és a 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 s'anomena
El conjunt de predicats sobre , denotats per , conté els següents predicats unaris:
true que és veritat per qualsevol pila sobre
bottom que és veritat per una pila el punter de la qual estigui apuntant al símbol de fons
que és veritat per alguna pila si
per tot .
El conjunt d'instruccions a , denotades com , contenen les següents funcions parcials:
id: que és la funció identitat a
pushn,γ : que donat una pila amb arbre afegeix un parell a l'arbre t i posa el punter de la pila a pn (és a dir, afegeix al fill número n) si pn no està dins el domini de t.
upn :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 :treu l'últim símbol on apunta el punter de la pila (mou el punter al pare de la posició actual)
setγ :reemplaça el símbol sota el punter per
per qualsevol enter positiu n i tot
Autòmat amb pila d'arbre
Un autòmat amb pila d'arbre és una 6-tupla A = (Q, Γ, Σ, qi, δ, Qf) on:
Q, Γ, i Σ son conjunts finits (estat, símbols de la pila i símbols d'entrada)
Una transició τ = (q1, u, p, f, q₂) és aplicable a una configuració (q, c, w) si
q1 = 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ó τ = (q1, 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 ∈ Qf i alguna pila amb arbre c tal que (qi, ci, w) ⊢* (q, c, ε) on
⊢* és la clausura reflexiva transitiva de ⊢ i
ci = (ti, ε) tal que ti assigna el símbol @ a ε i no està definit per altres casos.
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.
↑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.
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.