Algoritmo di Thompson

Questa voce o sezione sull'argomento informatica non è ancora formattata secondo gli standard.

Questa voce o sezione sull'argomento informatica è priva o carente di note e riferimenti bibliografici puntuali.

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.