Algoritmo de Thompson

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

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: 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 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:

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:

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:

Clausura ER AFND-e.jpg

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

Herramientas[editar]

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 mas 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:

Enlaces externos[editar]

Apunte de Gramaticas Regulares y Expresiones Regulares UNICEN