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 según el orden decreciente de exterioridad. El operador más externo corta 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 recursión creando (A)(B) – el contenido es solo indicativo, veremos cómo llenar A y B a medida que avanzamos.
Luego, al colocar la estrella en (B)*, aprovechamos la oportunidad para realizar la función OR en (A) = (a|b).
El siguiente paso es hacer la función OR en (B) = (C | D | E)
El proceso contenido al descender recursivamente 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)*
