Afnd a Afn

[pic]

Equivalencia de AFD y AFN
 Existe una equivalencia entre los AFD y AFN, de forma que un autómata M es equivalente a un autómata M' si L(M) ) L(M'). 
Ejemplo: Los autómatas de la siguiente figura son equivalentes. Obsérvese que uno es determinístico y el otro es no determinístico. Sin embargo, ambos aceptan las mismas cadenas.
 [pic] 
Ya que una función es un caso especial de relación(es decir, las funciones son relaciones que poseen requerimientos adicionales), las funciones de los AFD se consideran como relaciones en los AFN. En consecuencia, todo AFD es un AFN. La colección de lenguajes aceptados por los AFN incluye a todos los lenguajes aceptados por los AFD. De esto resulta que los AFN sólo aceptan los lenguajes aceptados por los AFD. Por lo tanto, los AFN no son máspotentes que los AFD con respecto a los lenguajes que aceptan.   
Transiciones
Podemos ampliar la definición de autómata finito no determinístico para incluir transiciones de un estado a otro que no dependan de ninguna entrada. Tales transiciones se llaman ε -Transiciones porque al realizarse no consumen ningún símbolo de entrada. Por ejemplo, los AFN de la siguiente
[pic]
 
[pic]
 
En el AFNdel inciso a), el autómata puede cambiar su estado de Q0 a Q1 sin consumir nada en la entrada. Obsérvese que Q1 es el único estado de aceptación de este AFN. Si w es cualquier cadena de 0 o más aes, este autómata cicla sobre Q0 hasta que consume las aes. Una vez que la cadena se vacía, se desplaza a Q1 y lo acepta. 
En el AFN del inciso b), el autómata puede moverse del estado Q2 al estado Q0 sinconsumir nada en la entrada. En ambos AFN, la decisión de elegir una ε -Transición se realiza de la misma forma que la de cualquier otra transición con elección múltiple que exista en un AFN (basándose en algo que no determina el modelo. Por tanto, las ε -Transiciones son consistentes con el matiz no determinístico de la versión que hemos dado del AFN. 
Si un AFN tiene ε -Transiciones, larelación de transición f asocia pares sobre L x ( I ∪ { ε } ) X L con subconjuntos de L. Es decir, f es una relación sobre L x ( I ∪ { ε } ) X L. Se puede añadir una columna en la tabla de f para colocar los pares de la forma (Si, ε ). Cuando hay ε -Transiciones en un AFN es conveniente suponer que cada estado tiene una ε -Transicion que se cicla en ese estado. Usaremos esto para sistematizar el cálculode los AFN. Es decir, el AFN del inciso a), tendría la siguiente tabla de transición
|f |a |b |ε |
|Q0 |{ Q1} |∅ |∅ |
|Q1 |∅ |{ Q2} |∅ |
|Q2 |{ Q0} |∅ |{ Q0} |

 

Conversión de un AFN en un AFD
 Paraconvertir un AFD en un AFN que reconozca el mismo lenguaje. Este algoritmo, a menudo es llamado construcción de subconjuntos, es útil para simular un AFN por medio de un programa de computadora.  
En la tabla de transiciones de un AFN, cada entrada es un conjunto de estados; en la tabla de transiciones de un AFD, cada entrada es tan solo un estado. La idea general tras la construcción AFN a AFD esque cada estado de AFD corresponde a un conjunto de estados del AFN. El AFD utiliza un estado para localizar todos los posibles estados en los que puede estar el AFN después de leer cada símbolo de la entrada. Es decir, después de leer la entrara a1, a2,. ..an, el AFD se encuentra en un estado que representa al subconjunto T de los estados del AFN alcanzables desde el estado de inicio del AFN alo largo de algún camino etiquetado con a1, a2,. ..an. El número de estados de AFD puede ser exponencialmente en el número de estados del AFN pero en la práctica este peor caso ocurre raramente. 
Algoritmo (Construcción de subconjuntos) Construcción de un AFD a partir de un AFN.
Entrada. Un AFN N
Salida. Un AFD D que acepta el mismo lenguaje
Método. El algoritmo construye una tabla de...