Hola, sea Σ = {a}, L = Σ* y un AFD que lo reconoce M = (Q,Σ,δ,q0,F) donde Q = {q0,q1}, Σ = {a}, F = {q0}, δ(q0, a) = q0, δ(q1, a) = q0.
Al aplicar el algoritmo de minimizacion visto en el curso q0 y q1 son distinguidos inmediatamente porque q0 es final y q1 no. Entonces Π0 = Π1 y el algoritmo termina con dos estados.
Sin embargo el segundo AFD M = (Q,Σ,δ,q0,F) donde Q = {q0}, Σ = {a}, F = {q0}, δ(q0, a) = q0. tambien reconoce L y tiene un solo estado.
Entonces mi pregunta es: Si un ejercicio esta escrito de la forma "minimize el siguiente AFD usando el algoritmo visto en el curso" como el practico 3 ejercicio 4 o "halle un autómata finito determinista mínimo equivalente" (sin especificar el algoritmo del curso) como en el practico 3 ejercicio 5. ¿Son diferentes? ¿Es en el primer caso correcto solo aplicar el algoritmo pero en el segundo debemos demostrar que hallamos el minimo (Usando por ejemplo el Corolario de Myhill - Nerode que si nos asegura eso)?