TALF 3: Autómatas Finitos

Paso de AFND a AFD

1. En Q' metemos {q0} y el nuevo estado inicial, q'0 es {q0}
2. Calculamos las transiciones con q'0 y cada símbolo. Los nuevos estados que aparezcan, los metemos en Q' (si son nuevos)
3. Marcamos q'0 para saber que se han calculado sus transiciones.
4. Mientras haya estados no marcados, cogemos uno y para cada símbolo, la func. de transición será:

• los estados a los que se llegue con el símbolo actual, a partir de cada estado que confomre el estado no marcado que acabamos de seleccionar.
• El resutlado lo metemos en Q' como un nuevo estado, y marcamos el estado del que acabamos de calcular sus trans
  

3. Yasta, y el nuevo F' contendrá todos los estados en los que alguno de sus componentes (estados originales del AFND) era final.

Paso de AFN-L a AFND

1. Para cada estado q del AFN-L, calcular la L-clausura, que es todos los estados a los que se puede llegar pasando solamente por arcos con L, partiendo de q.
2. La nueva función de transición:

• Para cada estado q y cada símbolo v, te coges la L-clausura de q que ya deberias tener calculada, y para cada estado de esos, ves a donde se llega con el simbolo v y lo añades a S. Tonces la L-clausura de S, es la nueva funcion de transición para (q, v).

3. El nuevo F' contiene el antiguo F y ademas, si alguno de los estados de L-clausura del estado inicial es final, tonces añadir el estado inicial a la nueva F'.

Obtener la ER a partir de un AF

1. Mu facil, se obtienen las ec. características de cada estado y se resuelve el sistema. La ER es la solución del estado inicial.
   
2. La ec. característica de un estado se construye poniendo

• estado = simbolo1.estado_al_que_lleva + simbolo2.estado_al_que_lleva

Y si el estado es final, tonces añadimos + L

Obtener el AF a partir de una ER