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]

Definició[modifica]

Pila amb arbre[modifica]

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$

Autòmat amb pila d'arbre[modifica]

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 \in Q$ és l'estat inicial,
$δ \subseteq fin. Q \times (Σ \cup {ε}) \times Pred(Γ) \times Instr(Γ) \times Q$ anomenats transicions, i
$Q f \subseteq 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 \in 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[modifica]

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]

Referències[modifica]

↑ 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.
↑ ^3,0 ^3,1 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.

[1] 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.

[2] 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.

[:0-3] 3,0 ^3,1 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.

[1]

[2]

[3]