Autómatas de estados finitos: estados finales

En nuestro curso de conceptos de lenguaje de programación, nuestro instructor afirmó que está bien que un estado final conduzca a otro estado en un diagrama de estado finito.

Pero esto parece ser un concepto fundamentalmente contradictorio. Debido a que un estado final por definición es uno que termina las transiciones, es decir, que una vez que lo alcanza, no queda nada más que hacer.

Y, sin embargo, presentó una diapositiva como esta, donde los estados finales están representados por dos círculos ... ¿Cómo es posible que B, D, E y H sean estados finales cuando claramente no lo son?

Parece que tiene una mala comprensión de los modelos generativos frente a los modelos de "reconocimiento".

La gramática que tiene a la derecha genera palabras aplicando reglas, comenzando desde la variable inicial y deteniéndose después de que no haya más variables.

Sin embargo, los autómatas reconocen un idioma de la siguiente manera: le das al autómata una palabra, letra por letra, y el autómata realiza transiciones en función de las letras que se le dan.

Si, después de leer todas las letras, el autómata termina en un estado de aceptación (también conocido como final), entonces decimos que el autómata acepta la palabra.

Por lo tanto, es mejor pensar en ellos como estados "de aceptación", en lugar de estados "finales", aunque ambos términos se usan comúnmente.

un estado final por definición es uno que termina las transiciones, es decir, que una vez que lo alcanza, no queda nada más que hacer.

La fuente de su confusión es que esta no es la definición. "Estado final" es una mala elección de nombre, y la mayoría de los autores parecen preferir "aceptar estado". La definición es que el autómata acepta si su ejecución finaliza en un estado final / de aceptación y rechaza lo contrario.

De hecho, es confuso! Para resolver su problema, llámelos estados "de aceptación" en lugar de estados "finales". Porque eso es lo que realmente son, solo un marcador que nos dice que en este momento la cadena procesada pertenece al lenguaje.

"un estado final por definición es uno que termina las transiciones, es decir, que una vez que lo alcanzas, no queda nada más que hacer".

En la convención tradicional de trabajar con aceptadores (es decir, autómatas de estado finito que le dicen si una cadena dada pertenece / no pertenece a un idioma), un estado final es aquel que, cuando se alcanza con una cadena vacía (la entrada fue consumido por completo) significa que se acepta la cadena inicial, es decir, es parte del lenguaje del autómata.

Como puedes ver. La gramática dada dice A -> a. Por lo tanto, el autómata acepta terminar en la cadena "a". Pero también permite A -> aB -> abD -> abc, por lo que también se acepta la cadena "abc". Si terminamos la cadena en este punto, estaremos en un estado final y, por lo tanto, la cadena fue aceptada. Pero aún podríamos querer que se acepte la cadena "ab". Por lo tanto, debemos asegurarnos de que {"a", "ab", "abc"} sean aceptados por el autómata. No vea los estados finales como un estado tal que si lo ingresamos nunca podremos abandonarlo, véalo como un estado para decirnos si nuestra cadena actual es aceptada o no.