Transformacion de afnd a afd

CONVERSION DE AUTOMATA FINITO NO DETERMINISTICO A AUTOMATA FINITO DETERMINISTICO
 
Expresión Regular
Una expresión regular es un método formal para describir un patrón y puede ser empleada paraconstruir un analizador de léxico que lo reconozca en una computadora. La expresión regular se convierte a un diagrama de transición y éste se puede representar como una tabla que conduzca el análisisde léxico. De hecho, la expresión sufre una serie de transformaciones para llegar a ser expresada como tabla:
Se convierte en

Se representa como
Se convierte en

Autómata Finito Nodeterministico (NFA) |

Autómata Finito Deterministico (DFA)
Tabla

|
|
|
|
|
|
|
AUTÓMATAS FINITOS
Un autómata finito es un conjunto de nodos y aristas que representantrayectorias para generar una expresión bajo un alfabeto. Un diagrama de transición es un autómata finito. Los autómatas finitos se clasifican en:
* Autómatas finitos no determinísticos. NFA
*Autómatas finitos determinísticos. DFA
AUTÓMATA FINITO NO DETERMINÍSTICO
Un NFA es un modelo matemático que consiste de:
* Un conjunto de estados.
* Un conjunto de símbolos de entrada.* Una función de transición que corresponde pares estado-símbolo a conjuntos de estados.
* Un estado So que denota como el estado inicial.
* Un conjunto de estados F que denotan losestados de aceptación o finales.
 
Un NFA no tiene restricciones para que exista más de una transición con el mismo nombre a diferentes estados, por lo que en una representación tabular no es posibledeterminar de manera única el estado destino para un símbolo determinado. Por ejemplo, el siguiente diagrama representa la expresión:

(a | b)* a b b

 

No podemos determinar a qué estado seavanza del estado 0 con el símbolo a; puede ser al propio 0 o al 1, No está determinado. Incluso podría existir transiciones sin ninguna restricción, que se denominan transiciones épsilon porque no...