Faire tourner l'automate sur une entrée, étape par étape

Simuler un automate, c'est simplement suivre, lettre par lettre, la suite d'états par laquelle il passe en lisant un mot donné - puis regarder l'état final pour savoir si le mot est accepté. Reprenons l'automate qui reconnaît les mots se terminant par «ab» (états q0 initial, q1, q2 acceptant, transitions rappelées dans la leçon précédente).

Simulons-le sur le mot «baab» :

Simulation de «baab»   (q0 initial, q1, q2 acceptant)

  lettre lue :        b        a        a        b
  etat avant :        q0       q0       q1       q1
  etat apres :        q0       q1       q1       q2

  etat final = q2  ->  ACCEPTE (q2 est acceptant)

À chaque étape, on part de l'état courant, on lit la lettre suivante, et la table de transitions donne le nouvel état. Ici, l'état final après les quatre lettres est q2, qui EST acceptant : le mot «baab» est donc accepté - et en effet, il se termine bien par «ab».

Comparons avec le mot «aba» :

Simulation de «aba»

  lettre lue :        a        b        a
  etat avant :        q0       q1       q2
  etat apres :        q1       q2       q1

  etat final = q1  ->  REJETE (q1 n'est pas acceptant)

Cette fois l'état final est q1, qui n'est PAS acceptant : le mot «aba» est rejeté. C'est cohérent, puisque «aba» se termine par «ba», pas par «ab» - même si le mot est PASSÉ par l'état acceptant q2 juste avant la dernière lettre.

Piège classique : arrêter la simulation trop tôt, dès que l'automate atteint un état acceptant, en pensant que "c'est bon, le mot est accepté". C'est faux : il faut lire le mot ENTIER jusqu'au bout, l'acceptation ne se décide que sur le tout dernier état atteint.

Autre piège, fréquent en début d'apprentissage : oublier de réinitialiser l'automate à l'état initial q0 avant de commencer une nouvelle simulation. Chaque mot est testé indépendamment, en repartant toujours de zéro.