Asdasd Asd Asd

1. Equivalencia entre autómatas

1.1 Equivalencia entre AFD y AFN
La equivalencia entre AFD y AFN es clara entendiendo todo AFD como un caso particular de un AFN. En el otro sentido, a partir un AFN A=(Q,, ,q0,F) se puede construir otro AFD A'=(Q',, ', q0', F') equivalente (que acepte el mismo lenguaje), de la siguiente forma:
* Q' = 2Q
* q0' = {q0}
* F' = { q'  Q' | q' F   }
* '(q',a) =  (q  q')(q,a) : q'  Q, a  

Figura 1. Autómata finito no determinista del ejemplo 1.
Ejemplo 1. Dado el autómata de la figura 1, el proceso de construcción de un AFD equivalente parte del estado inicial {q0}, y determina el conjunto de estados alcanzables con cada símbolo del alfabeto. De esta forma, por ejemplo, al considerar el símbolo a se alcanzan losestados {q0, q1, q2}.

Cada uno de los conjuntos de estados que aparezcan se considera como uno de los estados del AFD equivalente, determinandose para cada uno de ellos su función de transición. El proceso se repite mientras aparezcan nuevos estados. La figura 2 muestra la tabla de transiciones del AFD.
|
| a | b | c |
{q0} | {q0,q1,q2} | {q1,q2} | {q2} |
{q0,q1,q2} | {q0,q1,q2} |{q1,q2} | {q2} |
{q1,q2} |  | {q1,q2} | {q2} |
{q2} |  |  | {q2} |

Figura 2. Tabla de transiciones del AFD equivalente al AFN de la figura 1

a partir de esta tabla el diagrama de transiciones queda como muestra la figura 3.

Figura 3. Autómata finito determinista equivalente.
Ejemplo 2. Dado el AFN de la figura 4 la tabla de transiciones del AFD equivalente sería la mostrada en lafigura 5, con lo que el diagrama de transiciones del AFD quedaria como se muestra en la figura 6

Figura 4. AFN ejemplo.

|
| a | b | |
{q0} | {q0} | {q0,q1} | |
{q0,q1} | {q0} | {q0,q1,q2} | |
{q0,q1,q2} | {q0,q1,q2} | {q0,q1,q2} | |

Figura 5. Tabla de transiciones del AFD equivalente al AFN de la figura 4.

Figura 6. AFD equivalente al AFN de la figura.

El estado{q0,q1,q2} es el único estado final del AFD porque es el único que contiene el estado q2, estado final del AFN original.

1.2 Equivalencia entre AFD y AF
A partir de todo autómata finito no determinista con -transiciones A=(Q,, ,q0,F), se puede construir un AFD equivalente. Para ello seguiremos los siguientes pasos:
1. Obtener un AFN A'=(Q,,', q0, F') donde:
* F' = F  {q0}, si-clausura(q0)  F  
F' = F, si -clausura(q0)  F = .
* '(q,a) = (q,a) tomando a  , x  *, q  Q y donde:
(q,) = -clausura(q)
(q,xa) = -clausura ( (p  (q,x)) (p,a))

de esta forma A' no posee -transiciones.
2. A partir del AFN obtenido, aplicar el método de la sección 1.1 para obtener un AFD a partir de un AFN.

Figura 7. Ejemplo de autómata finito contransiciones vacias

Ejemplo 3. Dado el AF de la figura 7, representamos en la figura 8 su tabla de transiciones y la -clausura de cada estado.
|
| a | b | -clausura |
q0 |  | {q2} | {q0,q1} |
q1 | {q1} | {q3} | {q0,q1} |
q2 | {q1} | {q2,q3} | {q0,q1,q2} |
q3 |  |  | {q0,q1,q3} |

Figura 8. Tabla de transiciones y -clausura de cada estado del AF de la figura 7.

Paraobtener el conjunto de transiciones del AFN equivalente aplicaremos la construcción indicada al principio de la sección. Por ejemplo, para obtener el conjunto de transiciones del estado q0 con el símbolo b en el AFN equivalente:
* partiremos de la -clausura de q0 ({q0,q1})
* obtendremos los estados que se alcanzan a partir de {q0,q1} utilizando una b ({q2}  {q3})
* obtendremos la-clausura de este conjunto: -clausura({q2,q3}) = {q0,q1,q2}  {q0,q1,q3} = {q0,q1, q2, q3}

Procediendo de igual forma para todo q  Q y todo a  , obtenemos la tabla de transiciones del AFN sin transiciones vacias que se muestra en la figura 9. En este AFN, el único estado final es q3 porque -clausura(q0)  F = . Una vez obtenida la tabla de transiciones del AFN, se puede construir el...