# Autòmat per subprocessos

En teoria d'autòmats, un autòmat per subprocessos és un tipus estès d'una màquina d'estats finita que reconeix un llenguatge lleugerament sensible al context.

## Definició formal

Un autòmat per subprocessos és:
* un conjunt $N$ d'estats
* un conjunt $\Sigma$de símbols terminals
* un estat inicial $A_{S}\in N$
* un estat final $A_{F}\in N$
* un conjunt de camins $U$
* una funció parcial $\sigma :N\to U^{\perp }$on $U^{\perp }=U\{\perp \}{\text{ per}}\perp \notin U$
* un conjunt finit de transicions $\Theta$
Un camí $u_{1}...u_{n}\in U$ és una cadena de components de camí $u_{i}\in U$, on n pot ser 0, i el camí buit es denomina $\epsilon$. Un subprocés te la forma $u_{1}...u_{n}:A$ on $u_{1}...u_{n}\in U$és un camí i $A\in N$ és un estat. Un magatzem d'estats $S$ és un conjunt finit de camins, que es pot veure com una funció parcial de $U^{*}$ cap a $N$tal que $dom(S)$és tancat pel prefix.
Una configuració per un autòmat per subprocessos és una tripleta $\langle l,p,S\rangle$ on l denota la posició actual de la cadena d'entrada, p és el subprocés actiu i S és el magatzem de subprocessos que conte p. La configuració inicial és $\langle 0,\epsilon ,\{\epsilon :A_{S}\}\rangle$. La configuració final és $\langle n,u,\{\epsilon :A_{S},u:A_{F}\}\rangle$on n és la longitud de la cadena d'entrada i u abrevia $\sigma (A_{S})$. Una transició del conjunt $\Theta$pot ser de les formes següents i canvia la configuració de la següent manera:
* SWAP $B\rightarrow _{a}C$: consumeix el símbol d'entrada a i canvia l'estat del subprocés actiu de $\langle l,p,S\cup \{p:B\}\rangle$a $\langle l+1,p,S\cup \{p:C\}\rangle$
* SWAP $B\rightarrow _{\epsilon }C$: similar que l'anterior però no consumeix el símbol d'entrada a i canvia l'estat del subprocés actiu de $\langle l,p,S\cup \{p:B\}\rangle$a $\langle l,p,S\cup \{p:C\}\rangle$
* PUSH C: crea un nou subprocés i suspèn el seu subprocés pare, canvia l'estat: $\langle l,p,S\cup \{p:B\}\rangle$ a $\langle l,p,S\cup \{p:B,pu:C\}\rangle$on $u=\sigma (B)$ i $pu\notin dom(S)$
* POP [B]C: finalitza el procés actiu retornant el control al seu subprocés pare, canvia l'estat $\langle l,pu,S\cup \{p:B,pu:C\}\rangle$ a $\langle l,p,S\cup \{p:C\}\rangle$on $\sigma (C)=\perp$ i $pu\notin dom(S)$
* SPUSH [C] D: reactiva un subprocés suspès del subprocés actiu, canvia l'estat $\langle l,p,S\cup \{p:B,pu:C\}\rangle$a $\langle l,pu,S\cup \{p:B,pu:D\}\rangle$ on $u=\sigma (B)$
* SPOP [B] D: reactiva el procés pare del subprocés actiu, canvia l'estat $\langle l,pu,S\cup \{p:B,pu:C\}\rangle$ a $\langle l,p,S\cup \{p:D,pu:C\}\rangle$ on $\sigma (C)=\perp$
Es pot provar que $\sigma (B)=u$ per les transicions POP i SPOP i $\sigma (C)=\perp$per les transicions PUSH.
Una cadena d'entrada s'accepta per l'autòmat si hi ha una seqüència que canvia la configuració de l'estat inicial fins a l'estat final.

## Referències

* ↑ Villemonte de la Clergerie, Éric «Parsing Mildly Context-sensitive Languages with Thread Automata». COLING '02 Proceedings of the 19th international conference on Computational linguistics.. Association for Computational Linguistics [Stroudsburg, PA, USA], 2002, pàg. 1–7. DOI: 10.3115/1072228.1072256.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
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. :