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).

Algoritmo

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:

Archivo:Suma ER AFND-e.png

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

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

Archivo:Concat_ER_AFND-e.jpg

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:

Archivo:Clausura_ER_AFND-e.jpg

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

Herramientas

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

Enlaces externos

Apunte de Gramáticas Regulares y Expresiones Regulares UNICEN

Categoría:Lenguajes formales Thompson