Algoritmo di Thompson

L'algoritmo di McNaughton-Yamada-Thompson^[1] o algoritmo di costruzione di Thompson (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 prende il nome dal suo ideatore Ken Thompson.

Regole

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

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

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

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

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

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

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

Un' $\varepsilon$ -transizione connette lo stato iniziale e finale dell' NFA $N(e)$ . Un'altra $\varepsilon$ -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.