Construcción Thompson
El algoritmo de Thompson o construcción de Thompson permite construir un autómata no determinista con epsilon-transition de un expresión regular. El autómata se construye recursivamente a partir de patrones básicos:
Los elementos unitarios como ∅, ε y a son reconocidos por
Consideramos los operadores de la expresión regular R en orden decreciente de exterioridad. El operador más externo permite dividir R en R1 | R2, R1.R2 o R1 * que son reconocidos por
Aquí hay un ejemplo de construcción con la expresión (a | b) (a ∗ | ba ∗ | b ∗) ∗
Comenzamos la recursividad creando (A) (B); el contenido es solo indicativo, veremos cómo completar A y B a medida que avanzamos.
Luego, colocando la estrella en (B) *, aquí aprovechamos la oportunidad para hacer la función OR en (A) = (a | b).
El siguiente paso es hacer la función OR en (B) = (C | D | E)
El proceso se contuvo descendiendo de forma recursiva hasta obtener el autómata Thompson final.
Este último debe determinarse y minimizarse para una mejor lectura.
Algunos ejemplos sencillos
- 01∗
- (0 + 1)01
- 00(0 + 1)*
ES 
FR 
EN