Algoritmo di Thompson: differenze tra le versioni

Versione delle 17:12, 24 ago 2025

Versione attuale delle 23:08, 24 ago 2025

(Una versione intermedia di un altro utente non mostrate)

Riga 1:

{{N|informatica|aprile 2023}}

L{{'}}'''algoritmo di McNaughton-Yamada-Thompson'''<ref name="DragonBook">{{cita libro|autore1=Alfred Vaino Aho |autore2=Monica S. Lam |autore3=Ravi Sethi |autore4=Jeffrey D. Ullman |titolo=Compilers : Principles, Techniques, & Tools |data=2007 |editore=Pearson Addison-Wesley |città=Boston, MA, USA |isbn=9780321486813 |pp=159–163 |edizione=2 |urlcapitolo=https://www.pearson.com/us/higher-education/program/Aho-Compilers-Principles-Techniques-and-Tools-2nd-Edition/PGM167067.html |lingua=en |capitolo=3.7.4 Construction of an NFA from a Regular Expression |url=https://archive.org/details/compilers00alfr_0/page/159 }}</ref> o '''algoritmo di costruzione di Thompson''' (spesso indicato con '''TCA''' dall'[[Lingua inglese|inglese]] ''Thompson's construction clgorithmalgorithm'') è 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]].

Riga 32:

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

== Note ==

<references/>

== Bibliografia ==

* {{cita web|url=https://dl.acm.org/citation.cfm?doid=363347.363387|titolo=Programming Techniques: Regular expression search algorithm}}

== Altri progetti ==