Diseñar el AFN que acpeta el lenguaje en {a,b} en donde las palabras tienen longitud par y contienen la subcadena “aba”.

Al diseñar ducho autómata tenemos:

Convirtiendo a grafo AFD por medio de la tabla de estados tenemos:

Nuestra nueva tabla nos queda de la siguiente manera:

En donde los cuadros verdes representan las transición es de estados a probar para ver si nuestros diagrama se puede simplificar.

Probando para Q5 y Q2

Eliminando el estado Q5 y por consiguiente todas las transiciones que salen de él se eliminan y las que entran se redirigen al estado equivalente.

de dicha eliminación de estado concluimos que este autómata es equivalente y además como se hizo la eliminación del estado Q5, todos los estados que continene dicha fila serán distinguibles y por tanto nuestra tabla queda de la siguiente manera: en donde las X representan los estados distiguibles y el cuadrito azul significa que son los estados no distigibles

Si observamos los caso de la combinación de los estados (Q2,Q1) , (Q3,Q1), (Q3,Q2), se visualiza que al eliminar uno de los dos estados , uno de los estados del autómata queda volando, lo cual no es aceptable.

Probando con Q4 y Q2

Eliminando Q4

Por lo tanto nuestra tabla nos queda de la siguiente manera:

Como se puede observar nuestro diagrama final mostrado anteriormente es el autómata MC y para obtener a M aplicamos (MC)C quedando como nuestro diagrama final el siguiente: