Buenas, mi duda es la siguiente, al construir el AFND a partir del AFND-e, nuestro estado final era q3, pero como desde el estado inicial q0 puedo ir a q4 y de q4 a q3 mediante transiciones epsilon q0 pasa a ser estado final también pero porque q4 no?
hola:
eso queda implícito por el algoritmo, a través de la letra que se lee para llegar a ese estado. por ejemplo:
(q3) -- a--> (q4) -- éps--> ((qF))
g(q3, a) = eps-claus( g(eps-claus(q3), a) )
= eps-claus(g({q3}, a))
= eps-claus ({q4}) <--- acá entró en juego el épsilon
= {q4, qF}
quedaría entonces:
(q3) -- a--> (q4)
|--- a -----> ((qF))
luego, no precisás que q4 sea final, porque a partir de sus transiciones entrantes creamos atajos que saltan directamente al estado final qF. fijate que esto siempre es válido, por más épsilons encadenados que tengas, siempre que haya al principio una letra que dispare la "secuencia".
el tema con q0 es que hay una cadena de sólo épsilons, y no podemos tomar una transición con letra y hacer un atajo a qF con ella. necesitamos, entonces, modificar a q0 mismo y transformarlo en final para no dejar de reconocer a épsilon como perteneciente al lenguaje.
espero se haya entendido.
saludos,
d.-
Me quedo claro, muchas gracias!