Algoritmo di Thompson: differenze tra le versioni

Versione delle 17:12, 24 ago 2025

Versione delle 17:24, 24 ago 2025

Riga 1:

{{N|informatica|aprile 2023}}

L{{'}}'''algoritmo di McNaughton-Yamada-Thompson'''<ref name="DragonBook">{{cite book |language=en|author1=Alfred Vaino Aho |author2=Monica S. Lam |author3=Ravi Sethi |author4=Jeffrey D. Ullman |authorlink1=Alfred Aho |authorlink2=Monica S. Lam |authorlink3=Ravi Sethi |authorlink4=Jeffrey D. Ullman |title=Compilers : Principles, Techniques, & Tools |date=2007 |publisher=Pearson Addison-Wesley |___location=Boston, MA, USA |isbn=9780321486813 |page=[https://archive.org/details/compilers00alfr_0/page/159 159–163] |edition=2nd |chapter-url=https://www.pearson.com/us/higher-education/program/Aho-Compilers-Principles-Techniques-and-Tools-2nd-Edition/PGM167067.html |language=en |chapter-format=print |chapter=3.7.4 Construction of an NFA from a Regular Expression |url-access=registration |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 ==