Algoritmo di Thompson

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=\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.

Bibliografia

• Programming Techniques: Regular expression search algorithm, su dl.acm.org.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Algoritmo di Thompson