Algoritmo di Thompson
L'algoritmo di Thompson o algoritmo di costruzione (spesso indicato con TCA dall'inglese Thompson's construction clgorithm) è 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 rappresentiamo l'NFA equivalente all'espressione regolare .
L'espressione è rappresentata da
Un simbolo appartenente a un alfabeto di input è convertito dall'automa
L'espressione ottenuta dall'unione di due sottoespressioni è convertita da
Lo stato va tramite un' -transizione in uno stato iniziale di o . I loro stati finali divengono intermedi e si uniscono per mezzo di -transizioni 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 di 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.
Bibliografia
- Programming Techniques: Regular expression search algorithm, su dl.acm.org.
Altri progetti
Wikimedia Commons contiene immagini o altri file sull'algoritmo di costruzione di Thompson
