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 d'estats un conjunt de símbols terminals un estat inicial un estat final un conjunt de camins una funció parcial on un conjunt finit de transicions
Un camí és una cadena de components de camí , on n pot ser 0, i el camí buit es denomina . Un subprocés te la forma on és un camí i és un estat. Un magatzem d'estats és un conjunt finit de camins, que es pot veure com una funció parcial de cap a tal que és tancat pel prefix.
Una configuració per un autòmat per subprocessos és una tripleta 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 . La configuració final és on n és la longitud de la cadena d'entrada i u abrevia . Una transició del conjunt pot ser de les formes següents i canvia la configuració de la següent manera:
SWAP : consumeix el símbol d'entrada a i canvia l'estat del subprocés actiu de a SWAP : similar que l'anterior però no consumeix el símbol d'entrada a i canvia l'estat del subprocés actiu de a PUSH C: crea un nou subprocés i suspèn el seu subprocés pare, canvia l'estat: a on i POP [B]C: finalitza el procés actiu retornant el control al seu subprocés pare, canvia l'estat a on i SPUSH [C] D: reactiva un subprocés suspès del subprocés actiu, canvia l'estat a on SPOP [B] D: reactiva el procés pare del subprocés actiu, canvia l'estat a on
Es pot provar que per les transicions POP i SPOP i 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
Categoria:Autòmats Categoria:Computabilitat