Autómatas finitos deterministas (AFD) (tienen longitud impar o terminan en aaa)

Question

¿Es cierto mi intento o en qué me equivoco?

DFA : El conjunto de cadenas sobre $\{a, b\} $ que tienen longitud impar o terminan en $aaa$ .

Answer 1

Su autómata es correcto, pero no es mínimo. El autómata mínimo sólo tiene 5 estados. En realidad, puedes obtenerlo minimizando tu autómata. Entonces identificarás los estados 2 y 4, los estados 3 y 5 y los estados 6 y 8.

Answer 2

Tu DFA es correcto; consiste en ocho estados, como tú tienes, uno para cada combinación de "¿Es la cadena impar o de longitud par?" y "¿He visto más recientemente 0,1,2, o 3+ A's consecutivas?". Puedes organizar tu DFA así para facilitar la legibilidad:

Y hay un AFD equivalente con menos estados que podría ser más fácil de comprobar:

Answer 3

He aquí una manera de pensar en el lenguaje y en el autómata finito mínimo que lo describe:

Siempre que haya empezado a escribir una palabra $u$ Hay ocho casos que debe tener en cuenta cuando intente terminar la palabra con un sufijo $v$ de modo que toda la palabra $uv$ acabará en el idioma. Y en realidad, se dividen como $2 × 4$ casos:

¿Cuánto tiempo dura $u$ ?

• $u$ tiene un número par de letras.
• $u$ tiene un número impar de letras.

¿Cómo puede $u$ ¿Fin?

• $u$ no termina en $\mathtt a$ (por estar vacío o terminar en $\mathtt b$ ).
• $u$ termina en $\mathtt a$ (pero no en $\mathtt {aa}$ ).
• $u$ termina en $\mathtt {aa}$ (pero no en $\mathtt {aaa}$ ).
• $u$ termina en $\mathtt {aaa}$ (o en un sufijo con aún más $\mathtt a$ s).

Piénsalo, ¡es lo único que importa! Deberías intentar comprobar tú mismo tu autómata desde ese punto de vista. Intenta pensar que los estados de tu autómata codifican esa información.

(Si no lo consigues o necesitas otro par de ojos, deja un comentario).

Este punto de vista es una visión procedente de la Teorema de Myhill-Nerode .

---

Esta respuesta probablemente transmite la impresión de que se necesitan ocho estados para cualquier autómata que reconozca el lenguaje dado. Eso es porque yo pensaba así. Pero me equivoqué. No obstante, el procedimiento de mi respuesta sigue funcionando, e incluso se puede ver qué casos se comportan de la misma manera y, por tanto, deben considerarse equivalentes.