Algoritmo de Thompson

El algoritmo Thompson (también conocido como método de Thompson) creado por Ken Thompson y Dennis Ritchie, sirve para obtener autómatas finitos no deterministas con transiciones vacías (AFND-ε) a partir de expresiones regulares (ER).

Dadas las reglas que definen las expresiones regulares se pueden escribir como AFND-e:

• Φ es una expresión regular que describe el lenguaje vacío: en este caso se construye un AFND-e de dos estados, uno inicial y otro final, que no tienen transiciones, por lo cual no están conectados. De esta manera el autómata reconoce el lenguaje vacío.

• ε es una expresión regular que describe el lenguaje {ε}, que es un lenguaje que únicamente contiene la cadena vacía: el autómata que reconoce este lenguaje es aquel que el estado inicial también es final.

• si "a" esta en el alfabeto, "a" (sin comillas) es una expresión regular que describe el lenguaje {a}: el autómata que reconoce este lenguaje tiene definida una transición desde el estado inicial hacia un estado final.

• si existen r y s expresiones regulares r es una expresión regular que describe L(r) y s es una expresión regular que describe L(s)
  • r+s describe L(r) U L(s) (lenguaje generado por r union lenguaje generado por s)
  • r.s describe L(r). L(s) (lenguaje generado por r concatenado lenguaje generado por s)
  • r* describe L(r)* (lenguaje generado por r clausura)

Las precedencias de operador son *,., +.

Para el operador + de una ER el AFND-ε se arma de la siguiente manera:

Donde M1 y M2 son los AFND-ε que se suman.

Para el operador . de una ER el AFND-ε se arma de la siguiente manera:

Donde M1 y M2 son los AFND-ε que se concatenan.

Para el operador * de una ER el AFND-e se arma de la siguiente manera:

Donde M1 es el AFND-ε que se le aplica la clausura.

Existen varios programas que realizan este algoritmo y de hecho es habitual también pasar de AFND-e a AFND y de AFND a AFD, también suele ocurrir que el AFD no sea mínimo y se usa otro algoritmo para conseguir el AFD mínimo.

Cualquier ER puede ser reconocida por un AFD ya que los lenguaje regulares de tipo 3 son reconocidos por un AFD como autómata más restrictivo habiendo equivalencia entre no determinismo y determinismo. Generalmente los programas que aplican el algoritmo suelen transformar una ER a AFD mínimo.

Algunos programas son:

• Minerva Programado en java
• MTSolution

Apunte de Gramáticas Regulares y Expresiones Regulares UNICEN