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

Definició formal

Un autòmat per subprocessos és:

• un conjunt ${\displaystyle N}$ d'estats
• un conjunt ${\displaystyle \Sigma }$de símbols terminals
• un estat inicial ${\displaystyle A_{S}\in N}$
• un estat final ${\displaystyle A_{F}\in N}$
• un conjunt de camins ${\displaystyle U}$
• una funció parcial ${\displaystyle \sigma :N\to U^{\perp }}$on ${\displaystyle U^{\perp }=U\{\perp \}{\text{ per}}\perp \notin U}$
• un conjunt finit de transicions ${\displaystyle \Theta }$

Un camí ${\displaystyle u_{1}...u_{n}\in U}$ és una cadena de components de camí ${\displaystyle u_{i}\in U}$, on n pot ser 0, i el camí buit es denomina ${\displaystyle \epsilon }$. Un subprocés te la forma ${\displaystyle u_{1}...u_{n}:A}$ on ${\displaystyle u_{1}...u_{n}\in U}$és un camí i ${\displaystyle A\in N}$ és un estat. Un magatzem d'estats ${\displaystyle S}$ és un conjunt finit de camins, que es pot veure com una funció parcial de ${\displaystyle U^{*}}$ cap a ${\displaystyle N}$tal que ${\displaystyle dom(S)}$és tancat pel prefix.

Una configuració per un autòmat per subprocessos és una tripleta ${\displaystyle \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 ${\displaystyle \langle 0,\epsilon ,\{\epsilon :A_{S}\}\rangle }$. La configuració final és ${\displaystyle \langle n,u,\{\epsilon :A_{S},u:A_{F}\}\rangle }$on n és la longitud de la cadena d'entrada i u abrevia ${\displaystyle \sigma (A_{S})}$. Una transició del conjunt ${\displaystyle \Theta }$pot ser de les formes següents i canvia la configuració de la següent manera:

• SWAP ${\displaystyle B\rightarrow _{a}C}$: consumeix el símbol d'entrada a i canvia l'estat del subprocés actiu de ${\displaystyle \langle l,p,S\cup \{p:B\}\rangle }$a ${\displaystyle \langle l+1,p,S\cup \{p:C\}\rangle }$
• SWAP ${\displaystyle 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 ${\displaystyle \langle l,p,S\cup \{p:B\}\rangle }$a ${\displaystyle \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: ${\displaystyle \langle l,p,S\cup \{p:B\}\rangle }$ a ${\displaystyle \langle l,p,S\cup \{p:B,pu:C\}\rangle }$on ${\displaystyle u=\sigma (B)}$ i ${\displaystyle pu\notin dom(S)}$
• POP [B]C: finalitza el procés actiu retornant el control al seu subprocés pare, canvia l'estat ${\displaystyle \langle l,pu,S\cup \{p:B,pu:C\}\rangle }$ a ${\displaystyle \langle l,p,S\cup \{p:C\}\rangle }$on ${\displaystyle \sigma (C)=\perp }$ i ${\displaystyle pu\notin dom(S)}$
• SPUSH [C] D: reactiva un subprocés suspès del subprocés actiu, canvia l'estat ${\displaystyle \langle l,p,S\cup \{p:B,pu:C\}\rangle }$a ${\displaystyle \langle l,pu,S\cup \{p:B,pu:D\}\rangle }$ on ${\displaystyle u=\sigma (B)}$
• SPOP [B] D: reactiva el procés pare del subprocés actiu, canvia l'estat ${\displaystyle \langle l,pu,S\cup \{p:B,pu:C\}\rangle }$ a ${\displaystyle \langle l,p,S\cup \{p:D,pu:C\}\rangle }$ on ${\displaystyle \sigma (C)=\perp }$

Es pot provar que ${\displaystyle \sigma (B)=u}$ per les transicions POP i SPOP i ${\displaystyle \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