Construcción Thompson

Dificultad
Promedio 50%

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

construcción thompson

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

construcción thompson

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.

construcción thompson

Luego, colocando la estrella en (B) *, aquí aprovechamos la oportunidad para hacer la función OR en (A) = (a | b).

construcción thompson

El siguiente paso es hacer la función OR en (B) = (C | D | E)

construcción thompson

El proceso se contuvo descendiendo de forma recursiva hasta obtener el autómata Thompson final.

construcción thompson

Este último debe determinarse y minimizarse para una mejor lectura.

Algunos ejemplos sencillos

  1. 01
  2. (0 + 1)01
  3. 00(0 + 1)*
construcción thompson
Compartir, repartir
es_ESES