Automates à états finis: états finaux

Dans notre cours sur les concepts du langage de programmation, notre instructeur a affirmé qu'il est acceptable qu'un état final mène à un autre état dans un diagramme à états finis.

Mais cela semble être un concept fondamentalement contradictoire. Parce qu'un état final par définition est un état qui met fin aux transitions, c'est-à-dire qu'une fois que vous y êtes arrivé, il n'y a plus rien à faire.

Et pourtant, il a présenté une diapositive comme celle-ci, où les états finaux sont représentés par deux cercles ... Comment est-il possible que B, D, E et H soient des états finaux alors qu'ils ne le sont clairement pas?

Vous semblez avoir une mauvaise compréhension des modèles génératifs par rapport aux modèles "reconnaissants".

La grammaire que vous avez à droite génère des mots en appliquant des règles, en commençant par la variable initiale et en s'arrêtant après qu'il n'y ait plus de variables.

Les automates, cependant, reconnaissent une langue comme suit: vous alimentez l'automate un mot, lettre par lettre, et l'automate prend des transitions en fonction des lettres qui lui sont données.

Si, après avoir lu toutes les lettres, l'automate se retrouve dans un état d'acceptation (aka final), alors nous disons que l'automate accepte le mot.

Il est donc préférable de les considérer comme des États «acceptants» plutôt que comme des États «finaux», bien que les deux termes soient couramment utilisés.

un état final par définition est un état qui met fin aux transitions, c'est-à-dire qu'une fois que vous y êtes parvenu, il n'y a plus rien à faire.

La source de votre confusion est que ce n'est pas la définition. «État final» est un mauvais choix de nom, et la plupart des auteurs semblent préférer «État acceptant». La définition est que l'automate accepte si son exécution se termine dans un état final / acceptant et rejette autrement.

En effet, c'est déroutant! Pour résoudre votre problème, appelez-les états "acceptant" au lieu d'états "finaux". Parce que c'est ce qu'ils sont vraiment, juste un marqueur qui nous dit qu'à ce moment la chaîne traitée appartient au langage.

"un état final par définition est celui qui met fin aux transitions, c'est-à-dire qu'une fois que vous y êtes parvenu, il n'y a plus rien à faire."

Dans la convention traditionnelle de travailler avec des accepteurs (c'est-à-dire des automates à états finis qui vous indiquent si une chaîne donnée appartient / n'appartient pas à une langue), un état final est celui qui, lorsqu'il est atteint avec une chaîne vide (l'entrée était consommé entièrement) signifie que la chaîne initiale est acceptée, c'est-à-dire qu'elle fait partie du langage de l'automate.

Comme vous pouvez le voir. La grammaire donnée dit A -> a. Par conséquent, l'automate accepte de se terminer sur la chaîne "a". Mais il permet également A -> aB -> abD -> abc, donc la chaîne "abc" est également acceptée. Si nous terminons la chaîne à ce stade, nous serons dans un état final et la chaîne a donc été acceptée. Mais nous pourrions toujours vouloir que la chaîne "ab" soit acceptée. Nous devons donc nous assurer que {"a", "ab", "abc"} sont tous acceptés par l'automate. Ne voyez pas les états finaux comme un état tel que si nous y entrons, nous ne le quitterons jamais, voyez-le comme un état pour nous dire si notre chaîne actuelle est acceptée ou non.