Algoritmo di Thompson: differenze tra le versioni

Versione delle 05:40, 15 nov 2013

Versione attuale delle 23:08, 24 ago 2025

(23 versioni intermedie di 12 utenti non mostrate)

Riga 1:

{{N|informatica|aprile 2023}}

{{Voci senza uscita}}

L{{'}}''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 Constructionconstruction Algorithm.algorithm'') Derivaè un [[algoritmo]] che deriva un [[https://it.wikipedia.org/wiki/Automa_a_stati_finiti_non_deterministico|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 statoil inventatonome dadal suo ideatore [[https://it.wikipedia.org/wiki/Ken_Thompson|Ken Thompson]].

== Regole ==

Con <math>N(e)</math> rappresentiamo l'NFA equivalente all'espressione regolare '''<math>e'''</math>.

L' '''espressione <math>e=\varepsilon</math>''' è rappresentata da

[[File:Thompson-epsilon.svg|inlinecenter]]

Un '''simbolo <math>a</math> appartenente a un' [[Alfabeto (teoria dei linguaggi formali)|alfabeto]] di input''' è convertito dall'automa

[[File:Thompson-a-symbol.svg|inlinecenter]]

L' '''espressione ottenuta dall'unione di due sottoestressionisottoespressioni <math>e=s|t</math>''' è convertita da

[[File:thompson-or.svg|inlinecenter]]

Lo stato <math>q</math> va tramite un' <math>\varepsilon</math>-transazionetransizione in uno stato iniziale di <math>N(s)</math> o <math>N(t)</math>. I loro stati finali divengono intermedi e si uniscono per mezzo di <math>\varepsilon</math>-transazionitransizioni nello stato finale di N(e) chiamato <math>f</math>.

L' '''espressione formata dalla concatenazione di due sottoespressioni''' <math>e=st</math> si converte con

[[File:thompson-concat.svg|inlinecenter]]

Lo stato iniziale di <math>N(s)</math> è lo stato iniziale di N(e). Lo stato finale di <math>N(s)</math> diventa lo stato iniziale di <math>N(t)</math>. lo stato finale di <math>N(t)</math> è anche lo stato finale di <math>N(e)</math>.

La '''[[Star di Kleene|Kleene star]] sidi un'espressione''' <math>s^*</math> è convertita da

[[File:thompson-kleene-star.svg|inlinecenter]]

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 ==

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

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

{{Portale|informatica}}

{{Voci isolate}}

[[Categoria:LinguaggiTeoria dei linguaggi formali]]

[[Categoria:Teoria degli automi]]

[[Categoria:Algoritmi|Thompson]]