title: Algoritmo de Thompson
text: # 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).
  
  ## 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:
  
  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 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
  