Buenas, tengo una duda con respecto a los valores de δ.
Por ejemplo, en la parte 1, aparece que δ(r, 0) = {}.
Como defino un super estado que contenga a {}?
Por ejemplo, se definiría de esta manera ( [ ] ) al super estado que solo contiene a {}?
Buen día Agustín,
así es. Si cuando estás "procesando" las transiciones del AFND, estás en un caso donde las transiciones en cuestión van a "{}" (es decir no hay transiciones definidas), entonces eso se traducirá en que van a "[]". Por ejemplo, si estás procesando el superestado![[q_1q_3q_5]](https://eva.fing.edu.uy/filter/tex/pix.php/8d3b2969d26030353e6ba159a03e06cb.png "[q_1q_3q_5]")
y con una "a" todos van a "{}" entonces ![\delta([q_1q_3q_5],a) = []](https://eva.fing.edu.uy/filter/tex/pix.php/9bd029d5a62d36525cacbfe86d99a5d9.png "\delta([q_1q_3q_5],a) = []")
.
así es. Si cuando estás "procesando" las transiciones del AFND, estás en un caso donde las transiciones en cuestión van a "{}" (es decir no hay transiciones definidas), entonces eso se traducirá en que van a "[]". Por ejemplo, si estás procesando el superestado
y con una "a" todos van a "{}" entonces .Si luego de hacer todas las cuentas para hallar las transiciones del AFD te quedan algunas hacia "[]", entonces esas serán las transiciones que implícitamente irán al estado pozo. De hecho, si querés podés incluirlo, para que la función 
quede completamente definida.
quede completamente definida. Por poner un ejemplo rápido (genérico, y no relacionado con ningún ejercicio del práctico) sobre 
, si:
, si:![\delta(e_7,a) = []](https://eva.fing.edu.uy/filter/tex/pix.php/0a98669e369464f57fc6958f48a117d3.png "\delta(e_7,a) = []")
![\delta(e_8,b) = []](https://eva.fing.edu.uy/filter/tex/pix.php/9d639bd1f9c823ff70785005bc18ad57.png "\delta(e_8,b) = []")
![\delta(e_{10},a) = []](https://eva.fing.edu.uy/filter/tex/pix.php/a1aa35f7f58efe73f20878937c4db74e.png "\delta(e_{10},a) = []")
Entonces, la función se puede completar como:
se puede completar como:
Espero que quede claro y si no, como siempre, preguntá que la seguimos.
Saludos,
Santi
Saludos,
Santi
Hola, me queda una duda respecto a esto. Es necesario durante la conversión de AFND a AFD tener en cuenta ese estado pozo? o podemos simplemente decir que tal estado con tal valor no va a ningún lado y continuar? Se me genera esta duda cuando mas tarde a la hora de minimizar dice que la función de transición debe ser completa.
hola:
no, no es necesario considerar el estado pozo. es más, te recomiendo NO agregarlo en el algoritmo de "determinización".
la razón es muy simple, si tenés N estados en la entrada, la cantidad de estados resultantes puede llegar a 2^N. agregar un estado pozo te puede duplicar el tamaño del autómata con estados que son equivalentes a su contraparte con el pozo (pues el pozo, desde el punto de vista funcional, bajo cualquier circunstancia, nunca agrega un camino de aceptación).
saludos,
d.-
no, no es necesario considerar el estado pozo. es más, te recomiendo NO agregarlo en el algoritmo de "determinización".
la razón es muy simple, si tenés N estados en la entrada, la cantidad de estados resultantes puede llegar a 2^N. agregar un estado pozo te puede duplicar el tamaño del autómata con estados que son equivalentes a su contraparte con el pozo (pues el pozo, desde el punto de vista funcional, bajo cualquier circunstancia, nunca agrega un camino de aceptación).
saludos,
d.-
agrego:
sí es recomendable agregarlo para la minimización. aunque se podría obviar también, dado la cantidad de errores que puede inducir al aplicar el algoritmo, es FUERTEMENTE RECOMENDABLE que, en este caso, SIEMPRE lo agreguen.
sí es recomendable agregarlo para la minimización. aunque se podría obviar también, dado la cantidad de errores que puede inducir al aplicar el algoritmo, es FUERTEMENTE RECOMENDABLE que, en este caso, SIEMPRE lo agreguen.