Vés al contingut

Autòmat per subprocessos

De la Viquipèdia, l'enciclopèdia lliure

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

[modifica]

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

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