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

Una pila amb arbre amb punter 1,2 i domini {ε, 1, 42, 1.2, 1.5, 1.5.3}

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₁, 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.

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.