Algoritmo di Thompson: differenze tra le versioni

Versione delle 17:09, 24 ago 2025

Versione delle 17:09, 24 ago 2025

Riga 6:

== Regole ==

Con <math>N(e)</math> rappresentiamo l'NFA equivalente all'espressione regolare '''<math>e'''</math>.

L''''espressione <math>e=\varepsilon</math>''' è rappresentata da

[[File:Thompson-epsilon.svg|center]]

Un '''simbolo <math>a</math> appartenente a un alfabeto di input''' è convertito dall'automa

[[File:Thompson-a-symbol.svg|center]]

L''''espressione ottenuta dall'unione di due sottoespressioni <math>e=s|t</math>''' è convertita da

[[File:thompson-or.svg|center]]

Riga 22:

Lo stato <math>q</math> va tramite un' <math>\varepsilon</math>-transizione in uno stato iniziale di <math>N(s)</math> o <math>N(t)</math>. I loro stati finali divengono intermedi e si uniscono per mezzo di <math>\varepsilon</math>-transizioni nello stato finale di N(e) chiamato <math>f</math>.

L''''espressione formata dalla concatenazione di due sottoespressioni''' <math>e=st</math> si converte con

[[File:thompson-concat.svg|center]]

Riga 28:

Lo stato iniziale di <math>N(s)</math> è lo stato iniziale di N(e). Lo stato finale di <math>N(s)</math> diventa lo stato iniziale di <math>N(t)</math>. lo stato finale di <math>N(t)</math> è anche lo stato finale di <math>N(e)</math>.

La '''[[Star di Kleene|Kleene star]] di un'espressione''' <math>s^*</math> è convertita da

[[File:thompson-kleene-star.svg|center]]