Algoritmo di Thompson: differenze tra le versioni

Versione delle 13:32, 14 nov 2023

Versione attuale delle 23:08, 24 ago 2025

(8 versioni intermedie di 2 utenti non mostrate)

Riga 1:

{{W|informatica|novembre 2013}}

{{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 Constructionconstruction Algorithmalgorithm'') è 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 statoil inventatonome dadal suo ideatore [[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 sottoespressioni <math>e=s|t</math>''' è convertita da

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

Lo stato <math>q</math> va tramite un' <math>\varepsilon</math>-transizione 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>-transizioni 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]] di 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 ==

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

== Altri progetti ==

{{interprogetto|preposizione=sull'}}

{{WPortale|informatica|novembre 2013}}

[[Categoria:Teoria dei linguaggi formali]]