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.^[1][2] É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.^[3]

Per un conjunt finit i no buit ${\displaystyle \Gamma }$, una pila sobre ${\displaystyle \Gamma }$ és una tubla ${\displaystyle \langle t,p\rangle }$ on:

• t és una funció parcial de cadenes d'enters positius cap al conjunt ${\displaystyle \Gamma \cup }$@ amb un domini de prefix tancat (anomenat arbre)
• @ (anomenat símbol del fons) no és a ${\displaystyle \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 ${\displaystyle \Gamma }$ s'anomena${\displaystyle TS(\Gamma )}$

El conjunt de predicats sobre ${\displaystyle TS(\Gamma )}$, denotats per ${\displaystyle Pred(\Gamma )}$, conté els següents predicats unaris:

• true que és veritat per qualsevol pila sobre ${\displaystyle \Gamma }$
• bottom que és veritat per una pila el punter de la qual estigui apuntant al símbol de fons
• ${\displaystyle equals(\gamma )}$ que és veritat per alguna pila ${\displaystyle \langle t,p\rangle }$ si ${\displaystyle t(p)=\gamma }$

per tot ${\displaystyle \gamma \in \Gamma }$.

El conjunt d'instruccions a ${\displaystyle TS(\Gamma )}$, denotades com ${\displaystyle Instr(\Gamma )}$, contenen les següents funcions parcials:

• id: ${\displaystyle TS(\Gamma )\to TS(\Gamma )}$ que és la funció identitat a ${\displaystyle TS(\Gamma )}$
• push_n,γ : ${\displaystyle TS(\Gamma )\to TS(\Gamma )}$que donat una pila amb arbre ${\displaystyle \langle t,p\rangle }$afegeix un parell ${\displaystyle (pn\mapsto \gamma )}$a l'arbre t i posa el punter de la pila a pn (és a dir, afegeix ${\displaystyle \gamma }$al fill número n) si pn no està dins el domini de t.
• up_n :${\displaystyle 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 :${\displaystyle 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_γ :${\displaystyle TS(\Gamma )\to TS(\Gamma )}$reemplaça el símbol sota el punter per ${\displaystyle \gamma }$

per qualsevol enter positiu n i tot ${\displaystyle \gamma \in \Gamma }$

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₁, u, p, f, q₂) és aplicable a una configuració (q, c, w) si

• q₁ = 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₁, 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.

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.^[3]