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.