Algoritme de Thompson
El algoritme Thompson, també conegut com a método de Thompson, creat per Ken Thompson i Dennis Ritchie, servix per a obtindre autómates finitos no determinista en transicions buides (AFND-ε) a partir d'expressions regulars (ER).
Algoritme
[editar | editar còdic]Donades les regles que definixen les expressions regulars es poden escriure com AFND-i:
- Φ és una expressió regular que descriu el llenguage buit: en este cas es construïx un AFND-i de dos estats, un d'inicial i un atre final, que no tenen transicions, per lo que no estan conectats. D'esta manera l'autómata reconeix el llenguage buit.
- ε és una expressió regular que descriu el llenguage {ε}, que és un llenguage que únicament conté la cadena buida: l'autómata que reconeix este llenguage és aquell que l'estat inicial també és final.
si "a" esta en l'alfabet, "a" (sense comillas) és una expressió regular que descriu el llenguage {a}: l'autómata que reconeix este llenguage té definida una transició des de l'estat inicial cap a un estat final.
si existixen r i s expressions regulars r és una expressió regular que descriu L(r) i s és una expressió regular que descriu L(s)
- r+s descriu L(r) O L(s) (llenguage generat per r union llenguage generat per s)
- r.s descriu L(r). L(s) (llenguage generat per r concatenat llenguage generat per s)
- r* descriu L(r)* (llenguage generat per r clausura)
Les precedència d'operador són *,., +.
Per a l'operador + d'una ER el AFND-ε s'arma de la següent manera:
A on M1 i M2 són els AFND-ε que se sumen.
Per a l'operador . d'una ER el AFND-ε s'arma de la següent manera:
A on M1 i M2 són els AFND-ε que es concatenen.
Per a l'operador * d'una ER el AFND-i s'arma de la següent manera:
A on M1 és el AFND-ε que se li aplica la clausura.
Ferramentes
[editar | editar còdic]Existixen varis programes que realisen este algoritme i de fet és habitual també passar de AFND-i a AFND i de AFND a AFD, també sol ocórrer que el AFD no siga mínim i s'usa un atre algoritme per a conseguir el AFD mínim.
Qualsevol ER pot ser reconeguda per un AFD ya que els llenguage regulars de tipo 3 són reconeguts per un AFD com a autómata més restrictiu havent equivalència entre no determinisme i determinisme. Generalment els programes que apliquen l'algoritme solen transformar una ER a AFD mínim.
Alguns programes són:
- Minerva Programat en java
- MTSolution
- Este artícul conté una traducció derivada de «Algoritmo de Thompson» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.