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 $\mathrm{\Gamma }$', una pila sobre $\mathrm{\Gamma }$ és una tubla $⟨t,p⟩$ on:

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

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

• true que és veritat per qualsevol pila sobre $\mathrm{\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 $⟨t,p⟩$ si $t(p)=\gamma$

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

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

• id: $TS(\mathrm{\Gamma })\to TS(\mathrm{\Gamma })$ que és la funció identitat a $TS(\mathrm{\Gamma })$
• push_n,γ : $TS(\mathrm{\Gamma })\to TS(\mathrm{\Gamma })$que donat una pila amb arbre $⟨t,p⟩$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(\mathrm{\Gamma })\to TS(\mathrm{\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(\mathrm{\Gamma })\to TS(\mathrm{\Gamma })$treu l'últim símbol on apunta el punter de la pila (mou el punter al pare de la posició actual)
• set_γ :$TS(\mathrm{\Gamma })\to TS(\mathrm{\Gamma })$reemplaça el símbol sota el punter per $\gamma$

per qualsevol enter positiu n i tot $\gamma \in \mathrm{\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 Plantilla:Math on:

• Plantilla:Math, Plantilla:Math, i Plantilla:Math son conjunts finits (estat, símbols de la pila i símbols d'entrada)
• Plantilla:Math és l'estat inicial,
• Plantilla:Math anomenats transicions, i
• Plantilla:Math anomenats estats finals.

Una configuració d'Plantilla:Math és una tupla Plantilla:Math on:

• Plantilla:Math és un estat (l'estat actual),
• Plantilla:Math és una pila amb arbre
• Plantilla:Math és una paraula sobre Plantilla:Math

Una transició Plantilla:Math és aplicable a una configuració Plantilla:Math si

• Plantilla:Math,
• Plantilla:Math és cert a Plantilla:Math,
• Plantilla:Math es definida per Plantilla:Math, i
• Plantilla:Math és un prefix de Plantilla:Math.

La relació de transició d'Plantilla:Math és la relació binària Plantilla:Math de configuracions d'Plantilla:Math que és la unió de totes les relacions Plantilla:Math per una transició Plantilla:Math on, per tot Plantilla:Math és aplicable a Plantilla:Math, es te Plantilla:Math i Plantilla:Math s'obté de Plantilla:Math eliminant-hi el prefix Plantilla:Math.

El llenguatge d'Plantilla:Math és el conjunt de totes les paraules Plantilla:Math per les quals algun estat Plantilla:Math i alguna pila amb arbre Plantilla:Math tal que Plantilla:Math on

• Plantilla:Math és la clausura reflexiva transitiva de Plantilla:Math i
• Plantilla:Math tal que Plantilla:Math assigna el símbol @ a Plantilla:Math 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.