État, transition, état initial et états acceptants

Un automate fini est une machine abstraite très simple : elle est toujours dans un état parmi un nombre fini d'états possibles, et elle change d'état à chaque lettre qu'elle lit dans un mot. C'est un modèle fondamental de l'informatique théorique : il sert à décrire des motifs de texte, des protocoles réseau, des interfaces utilisateur, ou encore le fonctionnement interne d'un analyseur lexical de compilateur.

Quatre notions suffisent à tout définir :

• un ensemble d'états (les situations possibles dans lesquelles peut se trouver la machine) ;
• des transitions (des règles du type : depuis tel état, en lisant telle lettre, on va vers tel autre état) ;
• un état initial (l'unique état de départ, avant même d'avoir lu la moindre lettre) ;
• un ou plusieurs états acceptants (des états particuliers : si l'automate s'y trouve juste après avoir lu tout le mot, le mot est accepté, sinon il est rejeté).

Notation generale d'un automate :

  --> (q)       etat initial   (la flèche entrante ne vient d'aucun autre état)
      (q)       etat ordinaire
     ((q))      etat acceptant (double cercle)

     (q0) --x--> (q1)     (depuis q0, en lisant la lettre x, on va vers q1)

Un automate est dit déterministe (DFA) quand, pour chaque état et chaque lettre de l'alphabet, il existe exactement une transition possible : la machine ne peut jamais hésiter. C'est le cas le plus simple à exécuter et à comprendre - on l'oppose aux automates non déterministes (NFA), plus souples à construire mais qui autorisent plusieurs choix à la fois pour une même lettre.

Piège classique : confondre "état acceptant" et l'idée que l'automate s'arrêterait forcément d'y rester. En réalité, l'automate continue de lire des lettres même après être passé par un état acceptant ; seul l'état atteint APRÈS LA DERNIÈRE lettre du mot compte pour décider de l'acceptation.

Autre piège : oublier l'état initial. Deux automates avec les mêmes états et les mêmes transitions, mais des états initiaux différents, peuvent reconnaître des langages totalement différents.