Algoritmo di Thompson

Template:W Template:N L'algoritmo di Thompson o algoritmo di costruzione (spesso indicato con (TCA) dall'inglese Thompson's Construction Algorithm) è un algoritmo che deriva un automa a stati finiti non deterministico (NFA) da una qualunque espressione regolare dividendola nelle sue sottoespressioni elementari, che possono essere convertite direttamente per mezzo di un insieme di regole.

L'algoritmo è stato inventato da Ken Thompson.

Regole

Con $N(e)$ rappresentiamo l'NFA equivalente all'espressione regolare e.

L'espressione $e=\epsilon$ è rappresentata da

Un simbolo $a$ appartenente a un alfabeto di input è convertito dall'automa

inline

L'espressione ottenuta dall'unione di due sottoespressioni $e=s|t$ è convertita da

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

L'espressione formata dalla concatenazione di due sottoespressioni $e=st$ si converte con

inline

Lo stato iniziale di $N(s)$ è lo stato iniziale di N(e). Lo stato finale di $N(s)$ diventa lo stato iniziale di $N(t)$. lo stato finale di $N(t)$ è anche lo stato finale di $N(e)$.

La Kleene star di un'espressione $s^{*}$ è convertita da

inline

Un' $\epsilon$-transizione connette lo stato iniziale e finale dell' NFA $N(e)$. Un'altra $\epsilon$-transizione che va dallo stato finale a quello iniziale di $N(s)$ consente la ripetizione dell'espressione $s$ come da definizione dell'operatore Kleene star.

Bibliografia

• Template:Cita web