Algoritmo di Thompson

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.

Regole

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.

Note

1. ^ (EN) Alfred Vaino Aho, Monica S. Lam, Ravi Sethi e Jeffrey D. Ullman, 3.7.4 Construction of an NFA from a Regular Expression, in Compilers : Principles, Techniques, & Tools, 2ª ed., Boston, MA, USA, Pearson Addison-Wesley, 2007, pp. 159–163, ISBN 9780321486813.

Bibliografia

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

Altri progetti

Altri progetti

• Wikimedia Commons

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

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