Algoritmo de Thompson

De Wikipedia, la enciclopedia libre
Esta es una versión antigua de esta página, editada a las 21:16 21 dic 2013 por JacobRodrigues (discusión · contribs.). La dirección URL es un enlace permanente a esta versión, que puede ser diferente de la versión actual.

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

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.

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

Apunte de Gramaticas Regulares y Expresiones Regulares UNICEN

Obtenido de «https://es.wikipedia.org/w/index.php?title=Algoritmo_de_Thompson&oldid=71509002»