Algoritmo di Thompson

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

---

Sebbene vi siano una bibliografia e/o dei collegamenti esterni, manca la contestualizzazione delle fonti con note a piè di pagina o altri riferimenti precisi che indichino puntualmente la provenienza delle informazioni. Puoi migliorare questa voce citando le fonti più precisamente. Segui i suggerimenti del progetto di riferimento.

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.

Con ${\displaystyle N(e)}$ rappresentiamo l'NFA equivalente all'espressione regolare ${\displaystyle e}$.

L'espressione ${\displaystyle e=\varepsilon }$ è rappresentata da

Un simbolo ${\displaystyle a}$ appartenente a un alfabeto di input è convertito dall'automa

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

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

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

Lo stato iniziale di ${\displaystyle N(s)}$ è lo stato iniziale di N(e). Lo stato finale di ${\displaystyle N(s)}$ diventa lo stato iniziale di ${\displaystyle N(t)}$. lo stato finale di ${\displaystyle N(t)}$ è anche lo stato finale di ${\displaystyle N(e)}$.

La Kleene star di un'espressione ${\displaystyle s^{*}}$ è convertita da

Un' ${\displaystyle \varepsilon }$-transizione connette lo stato iniziale e finale dell' NFA ${\displaystyle N(e)}$. Un'altra ${\displaystyle \varepsilon }$-transizione che va dallo stato finale a quello iniziale di ${\displaystyle N(s)}$ consente la ripetizione dell'espressione ${\displaystyle s}$ come da definizione dell'operatore Kleene star.

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

• Wikimedia Commons contiene immagini o altri file sull'algoritmo di costruzione di Thompson

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica