Automates finis déterministes

Voici le cœur du cours, et l'objet le plus utile de toute l'année. Un automate fini est une machine d'une simplicité extrême — une poignée d'états, une flèche par lettre — et pourtant elle est partout : dans le premier étage de tout compilateur, dans la barre de recherche qui valide une adresse de courriel, dans le protocole réseau qui suit l'état d'une connexion, dans le distributeur de billets. Chaque fois qu'un programme doit reconnaître une forme dans un flux de symboles avec une mémoire bornée, il y a un automate fini, explicite ou caché.

Ce chapitre le définit, montre comment l'exécuter, et surtout comment en construire un pour un langage donné. Le mot d'ordre du bloc — implémenter plutôt que réciter — commence ici : à la fin, vous aurez codé le moteur d'un automate quelconque.

La définition : un quintuplet

Un automate fini déterministe (AFD) est la donnée de cinq éléments, notés $(Q, \Sigma, \delta, q_0, F)$ :

L'idée à retenir dès maintenant, et qui donne le sens de tout le reste : chaque état est une mémoire. Il ne mémorise pas les symboles déjà lus — un automate fini ne peut pas se souvenir de tout — mais la seule chose qui reste utile pour la suite : « où en suis-je de ma reconnaissance ? ». Comme $Q$ est fini, l'automate ne peut distinguer qu'un nombre fini de situations. C'est à la fois sa force et sa limite, et le chapitre 6 en tirera les conséquences.

Le déterminisme

Le mot « déterministe » a un sens précis : depuis un état donné, en lisant une lettre donnée, il y a exactement une transition possible. C'est l'exigence de fonction du chapitre 2 — une seule sortie par entrée. L'automate ne fait donc jamais de choix : à chaque instant, l'état courant et la lettre lue déterminent entièrement l'état suivant.

Cette propriété a une conséquence pratique majeure : l'exécution est rapide et simple. On lit le mot une seule fois, de gauche à droite, en suivant les flèches, sans jamais revenir en arrière ni explorer plusieurs possibilités. Le temps de reconnaissance est proportionnel à la longueur du mot — on ne fait pas mieux. C'est pourquoi les analyseurs lexicaux réels (chapitre 9) sont des AFD.

Exécution et acceptation

Exécuter un AFD sur un mot $w = a_1 a_2 \dots a_n$, c'est suivre un chemin :

1q0  --a1-->  q1  --a2-->  q2  --a3-->  ...  --an-->  qn

On part de $q_0$, on applique $\delta$ à chaque lettre, on arrive dans un état final $q_n$. Puis la règle d'acceptation, unique et sans nuance :

Le mot $w$ est accepté si et seulement si l'état d'arrivée $q_n$ appartient à $F$.

Sinon, il est rejeté. Le langage reconnu par l'automate $\mathcal{A}$, noté $L(\mathcal{A})$, est l'ensemble de tous les mots acceptés. Un langage est dit régulier s'il existe un automate fini qui le reconnaît — c'est la définition que tout le bloc II va explorer.

Notez le cas du mot vide $\varepsilon$ : l'automate ne lit aucune lettre, reste en $q_0$, et $\varepsilon$ est accepté exactement quand $q_0 \in F$. Encore une fois, tout se joue sur le statut du mot vide.

Construire un AFD : penser en situations

C'est le savoir-faire du chapitre, et il s'apprend par une seule question, posée à l'envers de l'intuition :

Quelles situations dois-je distinguer pour décider, à la fin, si j'accepte — et rien de plus ?

Chaque situation distincte devient un état. Prenons $L =$ « les mots sur $\{a, b\}$ contenant un nombre pair de $a$ ». Qu'ai-je besoin de retenir pendant la lecture ? Uniquement la parité du nombre de $a$ vus jusqu'ici. Deux situations, donc deux états :

1        b           b2       ┌──┐        ┌──┐3       ▼  │        ▼  │4   ──▶( pair )──a──▶( impair )5        ▲               │6        └───────a───────┘

• pair est l'état initial (zéro $a$, c'est pair) et le seul état acceptant ;
• lire un a bascule la parité ; lire un b ne change rien.

Plutôt que de l'imaginer, regardez-le fonctionner. L'animation ci-dessous fait lire le mot abba à cet automate : le ruban d'entrée défile en haut, l'état courant s'allume, et un jeton portant la lettre lue parcourt la transition prise. Comme abba contient deux a, le chemin revient à l'état pair et le mot est accepté.

Deux réflexes de conception valent d'être énoncés.

Distinguer juste ce qu'il faut. Retenir le nombre exact de $a$ demanderait une infinité d'états — impossible. Ne retenir que la parité suffit, parce que c'est la seule information qui sert à la décision finale. Un bon AFD oublie tout le reste.

Ni trop, ni trop peu d'états. Trop d'états distinguent des situations qui mènent au même comportement (gaspillage) ; trop peu confondent des cas qu'il fallait séparer (erreur). Le chapitre 6 donnera l'automate minimal, qui a le nombre exact d'états nécessaires.

L'automate complet

Un détail technique qui a des conséquences. Un AFD est complet si $\delta(q, a)$ est défini pour tout état $q$ et toute lettre $a$ : depuis n'importe quel état, chaque lettre a une flèche sortante. Notre exemple ci-dessus est complet.

Souvent, on dessine un automate incomplet : on omet les transitions qui « mènent à l'échec », pour ne pas surcharger le schéma. Pour le rendre complet, on ajoute un état puits (ou état poubelle) : un état non acceptant, absorbant, vers lequel partent toutes les transitions manquantes, et qui boucle sur lui-même. Une fois entré dans le puits, on n'en sort plus — le mot est condamné au rejet.

Pourquoi s'en soucier ? Parce que certaines constructions l'exigent. La plus importante : pour reconnaître le complément d'un langage — les mots que l'automate rejetait —, il suffit d'échanger les états acceptants et non acceptants. Mais cet échange ne donne le bon résultat que si l'automate est complet : sinon, un mot qui « bloquait » faute de transition ne serait ni dans le langage ni dans son complément. La complétude est le petit soin qui rend les propriétés de clôture du chapitre 6 correctes.

À vous

Le TP fondateur du bloc : implémenter un AFD. Vous écrivez d'abord le moteur d'exécution, une poignée de lignes qui exécute n'importe quel automate décrit par sa table de transition — la preuve que toute la logique du langage tient dans $\delta$, pas dans le code. Vous le testez sur « nombre pair de $a$ », puis vous concevez vous-même l'automate de « mots se terminant par $ab$ ».

C'est ce passage du papier au code que le programme du cours désigne comme le plus formateur : écrire le moteur fait comprendre l'automate mieux que n'importe quel exercice de tracé.

// Un AFD est un quintuplet (Q, Σ, δ, q0, F). On le décrit ici comme une
// donnée, et on écrit UNE fois le moteur qui exécute n'importe quel AFD.
//
// Langage visé : L = { mots sur {a,b} contenant un nombre PAIR de a }.

const afd = {
  etats: ["pair", "impair"],          // Q
  alphabet: ["a", "b"],               // Σ
  initial: "pair",                    // q0 : zéro 'a' lu, c'est pair
  acceptants: ["pair"],               // F
  // δ : table de transition. delta["etat"]["lettre"] = etat d'arrivée.
  delta: {
    pair:   { a: "impair", b: "pair" },   // lire un a change la parité ; b ne
    impair: { a: "pair",   b: "impair" }, // change rien
  },
};

// ── À VOUS (1) : le moteur d'exécution ──────────────────────────────────────
// Partir de l'état initial, lire le mot lettre par lettre en suivant δ,
// puis accepter si l'état final est dans F.
function accepte(afd, mot) {
  let etat = afd.initial;
  // à compléter : boucle sur les lettres de 'mot', mise à jour de 'etat'
  return false; // à remplacer : etat est-il acceptant ?
}

// ── Vérification ────────────────────────────────────────────────────────────
const tests = [
  ["",       true],   // 0 a : pair
  ["aa",     true],   // 2 a
  ["a",      false],  // 1 a
  ["abab",   true],   // 2 a
  ["baaab",  false],  // 3 a
  ["bbbb",   true],   // 0 a
];
for (const [mot, attendu] of tests) {
  const r = accepte(afd, mot);
  console.log("'" + mot + "'".padEnd(8) + " -> " + r + (r === attendu ? "  ok" : "  ✗"));
}

// ── À VOUS (2) : concevoir un AFD ───────────────────────────────────────────
// Décrivez ci-dessous un AFD 'afd2' pour L2 = { mots qui SE TERMINENT par 'ab' }.
// Indice : 3 états — "rien de spécial", "vient de voir un a", "vient de voir ab".
const afd2 = null; // à construire, sur le même modèle que 'afd'
if (afd2) {
  for (const mot of ["ab", "aab", "abab", "aba", "b", "ba"]) {
    console.log("L2 '" + mot + "' -> " + accepte(afd2, mot));
  }
}

function accepte(afd, mot) {
  let etat = afd.initial;
  for (const lettre of mot) {
    etat = afd.delta[etat][lettre];   // δ(etat, lettre) : une seule transition
  }
  return afd.acceptants.includes(etat);
}
// Le moteur tient en trois lignes, et il est GÉNÉRIQUE : il exécute n'importe
// quel AFD décrit par la donnée. C'est toute la force du modèle — la logique
// du langage est entièrement dans la table δ, pas dans le code.

// ── L'AFD pour « se termine par ab » ────────────────────────────────────────
const afd2 = {
  etats: ["q0", "qa", "qab"],
  alphabet: ["a", "b"],
  initial: "q0",
  acceptants: ["qab"],               // on accepte si on VIENT de lire ...ab
  delta: {
    // q0 : on n'a rien vu d'utile. Un 'a' amorce un possible "ab".
    q0:  { a: "qa",  b: "q0"  },
    // qa : on vient de voir un 'a'. Un 'b' complète "ab" ; un autre 'a' garde
    //      l'espoir (le dernier a peut encore commencer un ab).
    qa:  { a: "qa",  b: "qab" },
    // qab : on vient de voir "ab". Un 'a' relance (qa) ; un 'b' casse (q0).
    qab: { a: "qa",  b: "q0"  },
  },
};

// ── Ce que le TP enseigne ───────────────────────────────────────────────────
//
// 1. Chaque état est une MÉMOIRE : "où en suis-je de ma reconnaissance ?".
//    L'AFD ne peut retenir qu'un nombre FINI de situations — ici la parité des
//    a, ou les 2 derniers symboles utiles. C'est sa force (rapidité, mémoire
//    bornée) et sa limite (chapitre 6 : il ne sait pas compter jusqu'à n).
//
// 2. L'exécution est DÉTERMINISTE : depuis un état, une lettre mène à UN seul
//    état. Le moteur ne fait jamais de choix — d'où sa simplicité et sa
//    vitesse (une passe, temps proportionnel à la longueur du mot).
//
// 3. Concevoir un AFD, c'est répondre à : « quelles situations dois-je
//    distinguer, et rien de plus ? ». Trop d'états = on distingue l'inutile ;
//    trop peu = on confond des cas qu'il fallait séparer. Le chapitre 6
//    (minimisation) donnera le nombre EXACT d'états nécessaires.

Ce que la suite en fait

Vous savez maintenant ce qu'est un langage régulier — un langage reconnu par un AFD — et comment en construire un. Mais l'AFD est parfois pénible à concevoir directement : son exigence de déterminisme force à tout anticiper.

Le chapitre 4 lève cette contrainte avec l'automate non déterministe, bien plus facile à écrire, puis montre le résultat central du cours : on peut toujours transformer un automate non déterministe en AFD équivalent. C'est la déterminisation — le premier des deux points qui coincent, et celui où le $2^n$ de l'ensemble des parties (chapitre 2) va enfin se manifester.

À retenir

Exercices d'entraînement