Schéma d'un automate : cercles et flèches étiquetées

Le schéma est l'outil central pour comprendre un automate d'un coup d'oeil. La convention est universelle : chaque état est dessiné comme un cercle, chaque transition comme une flèche étiquetée par la lettre qui la déclenche, l'état initial reçoit une flèche entrante venue de nulle part, et un état acceptant se distingue par un double cercle.

Prenons un exemple concret : un automate qui reconnaît exactement les mots (sur l'alphabet {a, b}) qui SE TERMINENT par «ab». Trois états suffisent :

• q0 : état initial, rien d'utile lu encore ;
• q1 : le dernier caractère lu est un «a» (bon début de motif) ;
• q2 : les deux derniers caractères lus sont «a» puis «b» - motif trouvé, état acceptant.

Automate : mots qui se terminent par «ab»   (alphabet : a, b)

   etat initial                            etat acceptant
        |                                        ^
        v            a               b           |
  -->  (q0)  --------------> (q1)  --------------> (( q2 ))
        ^                       |
        |           a           |
        +-----------------------+   (boucle : q1 -> q1 en lisant «a»)

  (les autres transitions - q2 -> q1 sur «a», q2 -> q0 sur «b»,
   q0 -> q0 sur «b» - sont regroupées dans la table ci-dessous)

Table complete des transitions :
  etat      sur «a»            sur «b»
  q0        va vers q1         reste en q0
  q1        reste en q1        va vers q2
  q2        va vers q1         va vers q0

Legende :  --> (q0) = etat initial   |   (( q2 )) = etat acceptant (double cercle)

Lis bien les boucles de retour : depuis q1, si on relit un «a», on reste en q1 (rien n'est perdu) ; depuis q2, si on relit un «a», on redescend en q1 (on recommence à guetter un nouveau «ab») ; et un «b» depuis q0 ou q2 nous ramène en q0 (un «b» seul ne peut jamais commencer le motif).

Piège classique : oublier une transition. Un DFA complet doit avoir EXACTEMENT une flèche sortante par lettre de l'alphabet, pour chaque état - même quand elle "ne sert à rien" d'évident, comme le retour en q0 depuis q2 sur un «b». Un schéma incomplet ne décrit pas un DFA valide.

Autre piège : croire qu'un mot est accepté dès qu'il PASSE par l'état acceptant. Le mot «aba» passe par q2 après «ab», mais se termine en q1 après le dernier «a» : il est donc rejeté, car seul le tout dernier état compte.