Algoritmo di Thompson
L'algoritmo di Thompson o algoritmo di costruzione, spesso indicato con (TCA) dall'inglese Thompson's Construction Algorithm. Deriva un [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 [Thompson].
Regole
Con rappresentiamo l'NFA equivalente all'espressione regolare e.
L' espressione è rappresentata da
Un simbolo appartenente a un'alfabeto di input è convertito dall'automa
L' espressione ottenuta dall'unione di due sottoestressioni è convertita da
Lo stato va tramite un' -transazione in uno stato iniziale di o . I loro stati finali divengono intermedi e si uniscono per mezzo di -transazioni nello stato finale di N(e) chiamato .
L' espressione formata dalla concatenazione di due sottoespressioni si converte con
Lo stato iniziale di è lo stato iniziale di N(e). Lo stato finale di diventa lo stato iniziale di . lo stato finale di è anche lo stato finale di .
La Kleene star si un'espressione è convertita da
Un' -transizione connette lo stato iniziale e finale dell' NFA . Un'altra -transizione che va dallo stato finale a quello iniziale di consente la ripetizione dell'espressione come da definizione dell'operatore Kleene star.
