ALGORITMO THOMPSON

ALGORITMO 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 transicionesvací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 ellenguaje vacío: no hay AFD para este lenguaje ya que es 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 reconoceeste lenguaje es aquel que el estado inicial también es final.
sí "a" está en el alfabeto, "a" (sin comillas) es una expresión regular que describe el lenguaje {a}: el autómata que reconoce estelenguaje 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 quedescribe L(s)
r+s describe L(r) U L(s) (lenguaje generado por r unión 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 sesuman.
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.

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énsuele 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...