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

Le chapitre 3 a montré comment construire un AFD, et aussi sa difficulté : son déterminisme force à tout anticiper. Pour reconnaître « les mots qui se terminent par $ab$ », il faut prévoir, à chaque $a$ lu, qu'il pourrait être l'avant-dernière lettre — sans le savoir encore. Cette gymnastique est pénible et source d'erreurs.

L'automate non déterministe supprime cette gêne : il s'autorise à « deviner ». Il est bien plus facile à écrire — et c'est là qu'est le miracle du chapitre : cette liberté ne coûte aucune puissance. Tout automate non déterministe se transforme mécaniquement en AFD équivalent. La transformation s'appelle la déterminisation, et c'est le premier des deux points qui coincent de l'année. Il devient mécanique dès qu'on l'a fait tourner une fois — ce que fait l'exercice.

L'automate non déterministe

Un automate fini non déterministe (AFN) a la même définition qu'un AFD, à une différence près, mais décisive : la fonction de transition rend un ensemble d'états.

$\delta : Q \times \Sigma \to \mathcal{P}(Q).$

Depuis un état $q$ en lisant une lettre $a$, l'automate peut avoir plusieurs transitions possibles — ou aucune. Concrètement :

• $\delta(q, a) = \{q_1, q_2\}$ : deux choix possibles ;
• $\delta(q, a) = \emptyset$ : aucune transition — ce chemin meurt.

La règle d'acceptation change en conséquence, et c'est le point le plus important à comprendre :

Un AFN accepte un mot s'il existe au moins un chemin menant de l'état initial à un état acceptant.

Un seul chemin gagnant suffit. On peut imaginer l'automate explorant tous les chemins à la fois, en parallèle, et acceptant si l'un d'eux réussit. C'est cette lecture — « il existe un chemin » — qui rend les AFN si commodes : on écrit les transitions « utiles » et on laisse mourir les autres, sans se soucier d'un état puits.

Reprenons « se termine par $ab$ » en non déterministe :

1        a, b2       ┌──┐3       ▼  │4   ──▶( q0 )──a──▶( q1 )──b──▶(( q2 ))

En $q_0$, lire $a$ offre deux choix : boucler sur $q_0$ (« ce $a$ n'est pas le bon »), ou partir vers $q_1$ (« je parie que le $ab$ final commence ici »). L'automate n'a pas à trancher : si le pari est bon, le chemin $q_0 \to q_1 \to q_2$ existe et le mot est accepté. Comparez à l'AFD du chapitre 3, où il fallait gérer explicitement chaque cas : l'AFN dit simplement ce qu'on veut reconnaître.

L'animation déroule la lecture de aab. Observez la nouveauté par rapport au chapitre 3 : l'état courant n'est plus unique mais un ensemble — l'automate explore tous les chemins à la fois, et accepte dès que l'un d'eux atteint un état acceptant. À la fin, l'ensemble contient q2 : le mot est accepté. C'est déjà, en germe, l'idée de la déterminisation.

Les ε-transitions

Les AFN se dotent souvent d'un raccourci supplémentaire : les ε-transitions, des flèches étiquetées par le mot vide $\varepsilon$. Elles permettent de changer d'état sans lire aucune lettre.

1( q1 )──ε──▶( q2 )

Leur intérêt est purement pratique : elles servent à assembler des automates comme des pièces de Lego — brancher la sortie de l'un sur l'entrée d'un autre par une ε-transition, sans se soucier de raccorder les transitions. C'est exactement ce dont le chapitre 5 aura besoin pour construire un automate à partir d'une expression régulière (construction de Thompson).

Pour raisonner avec elles, on introduit l'ε-fermeture d'un état : l'ensemble de tous les états atteignables en ne suivant que des ε-transitions (y compris l'état lui-même). On l'intègre à la déterminisation ; l'idée générale reste la même, on ajoute simplement « et tout ce qu'on peut atteindre gratuitement par des $\varepsilon$ ».

La déterminisation : construction des sous-ensembles

Comment exécuter un automate qui « devine » sur une machine réelle, qui elle ne devine pas ? En le transformant en AFD. L'idée est d'une élégance qu'il faut avoir comprise une fois pour toutes :

Un état de l'AFD représente l'ensemble de tous les états où l'AFN pourrait se trouver après avoir lu le préfixe courant.

Le non-déterminisme « où suis-je ? — plusieurs réponses possibles » devient un déterminisme « je suis dans cet ensemble d'états — une seule réponse ». La question redevient à réponse unique, donc déterministe. La construction, dite des sous-ensembles, procède ainsi :

1. L'état initial de l'AFD est $\{q_0\}$ (avec son ε-fermeture s'il y a des ε-transitions).
2. Depuis un état-ensemble $E$, en lisant une lettre $a$, on va dans l'union des $\delta(e, a)$ pour tous les $e \in E$ : « tous les états où l'on peut arriver ».
3. Un état-ensemble est acceptant dès qu'il contient au moins un état acceptant de l'AFN — parce qu'il suffit qu'un chemin possible soit gagnant.
4. On ne construit que les ensembles réellement atteignables, en partant de $\{q_0\}$ et en suivant les transitions.

Le point 3 est le plus souvent raté : on accepte dès qu'un des états possibles est acceptant, pas quand ils le sont tous. C'est le reflet direct de la règle existentielle de l'AFN.

Le coût, et l'équivalence

Combien d'états peut avoir le déterminisé ? Ses états sont des sous-ensembles de $Q$. Si l'AFN a $n$ états, il y a au plus $2^n$ sous-ensembles — c'est le $2^n$ de l'ensemble des parties du chapitre 2, qui se manifeste enfin. C'est le prix théorique du non-déterminisme : la déterminisation peut faire exploser le nombre d'états.

Deux nuances tempèrent cette borne. En pratique, on ne construit que les ensembles atteignables, et ils sont presque toujours bien moins nombreux que $2^n$ — dans l'exercice, 3 sur 8. Mais le pire cas existe réellement : certains langages exigent bel et bien un nombre exponentiel d'états une fois déterminisés, et c'est pourquoi on garde parfois l'AFN tel quel.

Au-delà du coût, la conséquence est le théorème central du chapitre :

Tout AFN peut être transformé en un AFD reconnaissant le même langage. AFD et AFN reconnaissent donc exactement la même classe de langages : les langages réguliers.

Le non-déterminisme est plus commode à écrire, jamais plus puissant. C'est un confort de conception, pas une extension du modèle — et c'est un résultat profond, car on aurait pu croire le contraire.

À vous

L'exercice fait tomber le blocage en rendant l'algorithme mécanique : vous implémentez la construction des sous-ensembles, puis vous la faites tourner sur l'AFN de « se termine par $ab$ ». Vous voyez les états du déterminisé apparaître comme des ensembles $\{q_0\}$, $\{q_0, q_1\}$, $\{q_0, q_2\}$ — et la règle « acceptant = contient un acceptant » cesse d'être abstraite.

Codez-le, exécutez-le, relisez la trace : la déterminisation n'est plus un mystère mais une procédure que vous savez dérouler à la main.

// Un AFN reconnaît L = { mots sur {a,b} se terminant par 'ab' }.
// Non déterminisme : depuis q0, lire 'a' peut RESTER en q0 (boucle) OU aller
// en q1 (parier que le 'ab' final commence ici). δ rend un ENSEMBLE d'états.

const afn = {
  etats: ["q0", "q1", "q2"],
  alphabet: ["a", "b"],
  initial: "q0",
  acceptants: ["q2"],
  // delta[etat][lettre] = LISTE d'états (peut être vide, ou à plusieurs)
  delta: {
    q0: { a: ["q0", "q1"], b: ["q0"] },   // le choix est ici
    q1: { a: [],           b: ["q2"] },   // depuis q1, un 'b' complète "ab"
    q2: { a: [],           b: []      },
  },
};

// ── Outil : δ étendu à un ENSEMBLE d'états ──────────────────────────────────
// Depuis un ensemble E d'états, en lisant 'lettre', où peut-on être ?
// Réponse : l'union des δ(e, lettre) pour tout e dans E.
function transitionEnsemble(afn, ensemble, lettre) {
  const arrivee = new Set();
  for (const e of ensemble)
    for (const cible of afn.delta[e][lettre])
      arrivee.add(cible);
  return [...arrivee].sort();
}

// ── À VOUS : la construction des sous-ensembles ─────────────────────────────
// Construire l'AFD dont les états sont des ENSEMBLES d'états de l'AFN.
//   - état initial de l'AFD = { initial de l'AFN }
//   - depuis un état-ensemble, δ_AFD(E, lettre) = transitionEnsemble(...)
//   - un état-ensemble est acceptant s'il CONTIENT un acceptant de l'AFN
//   - on n'explore que les ensembles ATTEIGNABLES (pas les 2^n en aveugle)
function determiniser(afn) {
  const nom = (E) => "{" + E.join(",") + "}";
  const initial = [afn.initial];
  const aTraiter = [initial];
  const vus = new Set([nom(initial)]);
  const deltaAFD = {};
  const acceptantsAFD = [];

  while (aTraiter.length > 0) {
    const E = aTraiter.shift();
    // à compléter :
    //  1. si E contient un état de afn.acceptants, ajouter nom(E) aux acceptants
    //  2. pour chaque lettre, calculer l'ensemble d'arrivée A
    //     enregistrer deltaAFD[nom(E)][lettre] = nom(A)
    //     si nom(A) jamais vu, l'ajouter à 'vus' et 'aTraiter'
  }
  return { initial: nom(initial), acceptants: acceptantsAFD, delta: deltaAFD };
}

// ── Vérification ────────────────────────────────────────────────────────────
const afd = determiniser(afn);
console.log("État initial :", afd.initial);
console.log("Acceptants   :", afd.acceptants.join(" "));
console.log("Transitions :");
for (const [E, trans] of Object.entries(afd.delta))
  for (const [l, A] of Object.entries(trans))
    console.log("  " + E + " --" + l + "--> " + A);

function determiniser(afn) {
  const nom = (E) => "{" + E.join(",") + "}";
  const initial = [afn.initial];
  const aTraiter = [initial];
  const vus = new Set([nom(initial)]);
  const deltaAFD = {};
  const acceptantsAFD = [];

  while (aTraiter.length > 0) {
    const E = aTraiter.shift();
    deltaAFD[nom(E)] = {};
    // 1. acceptant si E contient AU MOINS un acceptant de l'AFN
    if (E.some((e) => afn.acceptants.includes(e))) acceptantsAFD.push(nom(E));
    // 2. une transition par lettre, vers l'ensemble atteignable
    for (const lettre of afn.alphabet) {
      const A = transitionEnsemble(afn, E, lettre);
      deltaAFD[nom(E)][lettre] = nom(A);
      if (!vus.has(nom(A))) { vus.add(nom(A)); aTraiter.push(A); }
    }
  }
  return { initial: nom(initial), acceptants: acceptantsAFD, delta: deltaAFD };
}

// ── Résultat, lu comme un AFD ───────────────────────────────────────────────
//   {q0}      --a--> {q0,q1}   --b--> {q0}
//   {q0,q1}   --a--> {q0,q1}   --b--> {q0,q2}   <- acceptant (contient q2)
//   {q0,q2}   --a--> {q0,q1}   --b--> {q0}
//
// L'AFN avait 3 états ; le déterminisé en a 3 ATTEIGNABLES sur 2^3 = 8
// possibles. On n'a exploré que les ensembles réellement atteints — c'est ce
// qui évite l'explosion dans la pratique.
//
// ── La clé pour ne plus être bloqué ─────────────────────────────────────────
//
// 1. Un état de l'AFD = « l'ENSEMBLE de tous les états où l'AFN pourrait se
//    trouver après avoir lu ce préfixe ». Le non-déterminisme « où suis-je ?
//    plusieurs réponses » devient un déterminisme « je suis dans CET ensemble,
//    une seule réponse ». C'est toute l'idée.
//
// 2. Acceptant = l'ensemble contient AU MOINS un acceptant de l'AFN. Car
//    l'AFN accepte s'il EXISTE un chemin acceptant : il suffit qu'un des états
//    possibles soit acceptant.
//
// 3. Au pire 2^n états (l'ensemble des parties, chapitre 2), mais on ne
//    construit que les ATTEIGNABLES — souvent bien moins. Le pire cas existe
//    pourtant réellement, et c'est pourquoi on préfère parfois garder l'AFN.
//
// 4. Conséquence théorique majeure : AFN et AFD reconnaissent EXACTEMENT les
//    mêmes langages. Le non-déterminisme est plus COMMODE à écrire, jamais
//    plus PUISSANT. C'est l'équivalence AFD/AFN.

Ce que la suite en fait

Vous disposez maintenant de deux descriptions équivalentes des langages réguliers : l'AFD (exécutable, efficace) et l'AFN (facile à écrire), reliés par la déterminisation.

Le chapitre 5 en ajoute une troisième, purement textuelle : les expressions régulières, celles que vous croisez déjà dans les éditeurs et les outils de recherche. Le théorème de Kleene établira qu'elles décrivent exactement les mêmes langages que les automates — et la construction de Thompson, qui traduit une expression en automate, s'appuiera précisément sur les ε-transitions vues ici pour assembler les pièces.

À retenir

Exercices d'entraînement

Vous connaissez déjà les expressions régulières sans le savoir : c'est la syntaxe \d{2}/\d{2} qui valide une date dans un formulaire, [a-z]+@[a-z]+\.[a-z]+ qui filtre une adresse de courriel, le motif tapé dans la recherche d'un éditeur de texte. Ce chapitre montre ce qu'elles sont vraiment — une troisième façon de décrire un langage régulier, purement textuelle — et révèle le résultat qui unifie tout le bloc II : le théorème de Kleene, qui affirme qu'expressions régulières et automates finis décrivent exactement les mêmes langages.

Trois descriptions, un seul monde. C'est l'un des plus beaux résultats du cours, et le plus utile en pratique.

Syntaxe : trois opérations et rien d'autre

Une expression régulière sur un alphabet $\Sigma$ se construit inductivement (chapitre 2), à partir de briques élémentaires et de trois opérations. Les briques :

• $\emptyset$ dénote le langage vide ;
• $\varepsilon$ dénote le langage $\{\varepsilon\}$ ;
• une lettre $a \in \Sigma$ dénote $\{a\}$.

Les opérations, appliquées à des expressions déjà construites :

La priorité se lit comme en arithmétique : l'étoile est le « puissance », la concaténation le « produit », l'union la « somme ». Ainsi $ab^* \mid c$ se lit $\big(a(b^*)\big) \mid c$, et les parenthèses servent à forcer un autre regroupement, comme dans $(a \mid b)^*$.

Ce sont exactement les trois opérations sur les langages du chapitre 1. Une expression régulière n'est rien d'autre qu'une notation compacte pour les combiner — pas un mécanisme nouveau.

Sémantique : le langage dénoté

À chaque expression $E$ correspond un langage $L(E)$, défini en suivant sa construction :

Lisons quelques exemples sur $\Sigma = \{a, b\}$ — cette lecture est le savoir-faire du chapitre :

• $ab$ dénote $\{ab\}$ — un seul mot ;
• $a \mid b$ dénote $\{a, b\}$ — « $a$ ou $b$ » ;
• $a^*$ dénote $\{\varepsilon, a, aa, aaa, \dots\}$ — noter que $\varepsilon$ en fait partie ;
• $(a \mid b)^*$ dénote tous les mots sur $\{a, b\}$, c'est-à-dire $\Sigma^*$ ;
• $(a \mid b)^* ab$ dénote « tous les mots qui se terminent par $ab$ » — le langage même des chapitres 3 et 4, décrit ici en cinq symboles.

Ce dernier exemple mérite qu'on s'y arrête : ce que l'AFD du chapitre 3 exprimait par trois états et six transitions tient en une courte expression. C'est la force de la notation — mais rappelez-vous qu'elle décrit exactement le même langage, ni plus ni moins.

Deux pièges classiques, tous deux liés au chapitre 1 :

• L'étoile inclut toujours le mot vide. $L(E^*)$ contient $\varepsilon$ même si $\varepsilon \notin L(E)$ — la concaténation de « zéro copie ». Oublier ce cas fausse la moitié des exercices.
• $\emptyset$ et $\varepsilon$ ne sont pas la même chose. $\emptyset^* = \{\varepsilon\}$, tandis que $\emptyset$ tout court dénote le langage vide. C'est la distinction du chapitre 1, qui revient à l'identique.

Le théorème de Kleene

Voici le résultat qui referme le bloc et justifie tout ce qui précède :

Théorème de Kleene. Un langage est décrit par une expression régulière si et seulement si il est reconnu par un automate fini.

Les trois descriptions — AFD, AFN, expression régulière — sont donc équivalentes : elles définissent une seule et même classe, les langages réguliers. C'est pourquoi on peut passer librement de l'une à l'autre selon ce qui est commode : écrire une expression régulière (concis), la transformer en automate pour l'exécuter efficacement (rapide), raisonner sur l'automate pour prouver une propriété.

La preuve se fait dans les deux sens, et chaque sens est une construction algorithmique — pas seulement une existence. C'est ce qui la rend utile : elle donne les recettes qu'emploient les outils réels.

D'une expression à un automate : Thompson

Le sens « expression → automate » emploie la construction de Thompson. Elle procède inductivement, exactement selon la structure de l'expression, en assemblant de petits AFN avec des ε-transitions (chapitre 4) — dont c'est ici l'usage principal :

• une lettre $a$ : deux états reliés par une flèche $a$ ;
• une union $E \mid F$ : un nouvel état initial pointe par $\varepsilon$ vers les automates de $E$ et de $F$ (les deux branches de l'alternative) ;
• une concaténation $E \cdot F$ : la sortie de l'automate de $E$ est branchée par $\varepsilon$ sur l'entrée de celui de $F$ ;
• une étoile $E^*$ : on ajoute des ε-transitions pour pouvoir répéter l'automate de $E$ ou le sauter (le cas « zéro copie »).

Le résultat est un AFN avec ε-transitions, qu'on rend déterministe par la construction du chapitre 4 si l'on veut l'exécuter. C'est très exactement la chaîne qu'un moteur d'expressions régulières parcourt en interne.

D'un automate à une expression : élimination d'états

Le sens inverse, « automate → expression », emploie l'élimination d'états. On retire les états un par un ; à chaque retrait, on reporte l'information perdue sur les transitions restantes, en les étiquetant non plus par des lettres mais par des expressions régulières. À la fin, il ne reste qu'une transition de l'entrée à la sortie, étiquetée par l'expression régulière cherchée.

Vous n'avez pas à mémoriser les détails de ces deux constructions en L2 ; vous devez retenir qu'elles existent, qu'elles sont effectives (on peut les programmer), et qu'ensemble elles prouvent le théorème de Kleene par double construction.

À vous

L'exercice donne aux expressions régulières leur sens en code. Vous implémentez la sémantique — chaque opérateur (union, concaténation, étoile) est l'opération correspondante sur les langages du chapitre 1 — puis vous calculez le langage de $(a \mid b)^* ab$ et vérifiez quels mots il contient.

L'étoile vous forcera à traiter le cas « zéro copie » : oublier le mot vide initial rend l'opération fausse. Et vous devrez borner par une longueur, parce que le langage est infini — une petite expression décrit un langage sans fin, tout comme un automate avec ses boucles. C'est là, concrètement, le théorème de Kleene.

// Une expression régulière décrit un LANGAGE. Ici on la représente par un
// arbre, et on calcule le langage qu'elle dénote — jusqu'à une longueur max,
// car l'étoile produit un ensemble infini.
//
// Opérateurs (rappel chapitre 1) :
//   lettre  -> { "a" }              vide -> {}          epsilon -> { "" }
//   union(E,F)  = L(E) ∪ L(F)
//   concat(E,F) = L(E) · L(F)   (tous les u·v, u∈L(E), v∈L(F))
//   etoile(E)   = L(E)*         (zéro, un ou plusieurs mots de L(E))

// Constructeurs d'arbre :
const lettre = (c) => ({ type: "lettre", c });
const epsilon = { type: "epsilon" };
const vide = { type: "vide" };
const union  = (g, d) => ({ type: "union", g, d });
const concat = (g, d) => ({ type: "concat", g, d });
const etoile = (e) => ({ type: "etoile", e });

// ── À VOUS : la sémantique ──────────────────────────────────────────────────
// langage(expr, max) rend l'ENSEMBLE (Set) des mots de longueur <= max décrits
// par expr.
function langage(expr, max) {
  switch (expr.type) {
    case "vide":    return new Set();          // aucun mot
    case "epsilon": return new Set([""]);      // le seul mot vide
    case "lettre":  return new Set([expr.c]);  // un seul mot d'une lettre
    case "union": {
      // à compléter : réunir les deux langages
      return new Set();
    }
    case "concat": {
      // à compléter : tous les u+v (u du gauche, v du droit), longueur <= max
      return new Set();
    }
    case "etoile": {
      // à compléter : ε, puis L, puis L·L, ... tant que la longueur <= max
      return new Set();
    }
  }
}

// ── L'expression (a|b)*ab  :  « se termine par ab » ─────────────────────────
const expr = concat(etoile(union(lettre("a"), lettre("b"))), concat(lettre("a"), lettre("b")));

const mots = [...langage(expr, 3)].sort((x, y) => x.length - y.length || x.localeCompare(y));
console.log("(a|b)*ab, mots de longueur <= 3 :");
console.log("  [" + mots.join(", ") + "]");
console.log("  ab present ?", mots.includes("ab"));   // attendu true
console.log("  aab present ?", mots.includes("aab")); // attendu true
console.log("  ba present ?", mots.includes("ba"));   // attendu false

function langage(expr, max) {
  switch (expr.type) {
    case "vide":    return new Set();
    case "epsilon": return new Set([""]);
    case "lettre":  return new Set([expr.c]);
    case "union": {
      const g = langage(expr.g, max), d = langage(expr.d, max);
      return new Set([...g, ...d]);              // ∪
    }
    case "concat": {
      const g = langage(expr.g, max), d = langage(expr.d, max);
      const r = new Set();
      for (const u of g) for (const v of d)
        if (u.length + v.length <= max) r.add(u + v);   // ·, borné
      return r;
    }
    case "etoile": {
      // ε toujours (zéro copie), puis on ajoute L·(ce qu'on a déjà) tant
      // que ça grandit et que la longueur reste <= max.
      const base = langage(expr.e, max);
      const r = new Set([""]);
      let frontiere = new Set([""]);
      while (frontiere.size > 0) {
        const suivante = new Set();
        for (const u of frontiere) for (const v of base) {
          const w = u + v;
          if (w.length <= max && !r.has(w)) { r.add(w); suivante.add(w); }
        }
        frontiere = suivante;
      }
      return r;
    }
  }
}
// (a|b)*ab, longueur <= 3 : ab, aab, bab, abab n'apparaît pas (longueur 4).
// → [ab, aab, bab]. « ab » et « aab » présents, « ba » absent. ✓

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. Une expression régulière n'est PAS de la magie de recherche : c'est une
//    notation pour trois opérations sur les langages du chapitre 1 — union,
//    concaténation, étoile de Kleene. Chaque case du switch EST une de ces
//    opérations. Comprendre une regex = savoir quel langage elle dénote.
//
// 2. L'étoile force à gérer le cas « zéro copie » (ε ∈ L* toujours) — le
//    piège du chapitre 1 ressort ici : oublier le new Set([""]) initial rend
//    l'étoile fausse.
//
// 3. On a dû BORNER par une longueur max : le langage de (a|b)*ab est infini.
//    Une expression finie décrit un langage potentiellement infini — c'est
//    précisément ce que fait aussi un automate avec ses boucles, et le
//    théorème de Kleene dit que ce sont les MÊMES langages.

Ce que la suite en fait

Le bloc II tient debout : trois descriptions équivalentes des langages réguliers, reliées par des constructions effectives. Une question reste ouverte, et c'est la plus importante — tous les langages sont-ils réguliers ?

Le chapitre 6 y répond, et la réponse est non. Il donne d'abord l'outil pour ranger un automate (la minimisation), recense ce que la classe régulière sait faire (les propriétés de clôture), puis l'outil qui prouve qu'un langage échappe aux automates : le lemme de pompage, second point qui coince de l'année, avec son exemple canonique $a^n b^n$ — celui-là même que l'exercice du chapitre 1 avait déjà mis de côté.

À retenir

Exercices d'entraînement

Le bloc II touche à sa fin avec la question la plus profonde du cours. Jusqu'ici, chaque langage rencontré était régulier — on lui trouvait un automate. Mais est-ce toujours le cas ? Tous les langages sont-ils réguliers ?

La réponse est non, et savoir le prouver est le second point qui coince de l'année. Ce chapitre y mène en trois temps : d'abord un outil pour obtenir l'automate le plus économe (la minimisation), ensuite l'inventaire de ce que la classe régulière sait faire (les propriétés de clôture), enfin l'outil qui trace sa frontière (le lemme de pompage), avec l'exemple que le chapitre 1 avait mystérieusement mis de côté : $a^n b^n$.

La minimisation

Pour un langage régulier donné, il existe une infinité d'automates qui le reconnaissent — on peut toujours ajouter des états inutiles. Mais il en existe un seul de taille minimale, à renommage près : l'automate minimal. La minimisation est la procédure qui le trouve.

L'idée repose sur la relation d'équivalence du chapitre 2. Deux états sont indistinguables si, depuis l'un ou l'autre, exactement les mêmes mots mènent à l'acceptation — les fusionner ne change rien au langage reconnu. La minimisation regroupe les états indistinguables en classes d'équivalence, chaque classe devenant un état unique du minimal.

Deux usages justifient ce travail :

• Comparer deux langages. Deux automates reconnaissent le même langage si et seulement si leurs minimaux sont identiques (à renommage près). C'est le test d'équivalence, sinon délicat.
• Optimiser. Un analyseur lexical avec le moins d'états possible est plus rapide et plus léger — ce qui compte au chapitre 9.

Retenez surtout le résultat d'existence : à chaque langage régulier correspond un automate minimal unique, qui en est en quelque sorte l'empreinte.

Les propriétés de clôture

Une classe de langages est close par une opération si, en l'appliquant à des langages de la classe, on reste dans la classe. Les langages réguliers sont remarquablement stables :

Ces clôtures ne sont pas de simples curiosités : ce sont des outils de preuve. Elles permettent de construire de nouveaux langages réguliers sans repartir de zéro — et, retournées, de prouver la non-régularité. Si $L_1 \cap L_2$ n'était pas régulier alors que $L_2$ l'est, on en déduirait que $L_1$ ne l'est pas ; c'est une technique de repli quand le lemme de pompage est malcommode à appliquer directement.

Le complément mérite un rappel : sa clôture exige un automate complet (chapitre 3). C'est là que le soin apporté à l'état puits porte ses fruits.

Le lemme de pompage

Voici l'outil central du chapitre, et l'un des plus subtils de l'année. Il repose sur une intuition simple qu'il faut avoir en tête avant la formule :

Un automate fini a un nombre fini d'états, donc une mémoire bornée. S'il lit un mot plus long que son nombre d'états, il repasse forcément par un même état — et la portion de mot lue entre ces deux passages forme une boucle que l'on peut répéter à volonté.

C'est le principe des tiroirs : plus de lettres que d'états, donc un état revisité.

L'animation rend cette boucle visible. L'automate ci-dessous compte les a modulo 3 ; sur le mot aaa, son chemin r0 → r1 → r2 → r0 revient à son point de départ. Ce cycle est exactement le facteur $y$ que le lemme « pompe » : puisqu'il ramène au même état, on peut le répéter (aaaaaa) ou le retirer (ε) sans jamais quitter le langage. Retenez l'image — c'est tout le mécanisme du lemme.

Formellement :

Lemme de pompage. Si $L$ est régulier, alors il existe une longueur $p$ (la « longueur de pompage ») telle que tout mot $w \in L$ avec $|w| \geq p$ peut s'écrire $w = xyz$ avec :

• $|xy| \leq p$,
• $|y| \geq 1$ (le facteur $y$ n'est pas vide),
• et pour tout $i \geq 0$, le mot $xy^iz$ appartient encore à $L$.

Autrement dit, la boucle $y$ peut être répétée ($i \geq 2$), supprimée ($i = 0$), ou laissée telle quelle ($i = 1$), sans jamais sortir du langage. « Pomper » $y$, c'est jouer sur ce $i$.

L'utiliser : un jeu, et un sens de lecture

Le lemme sert dans un seul sens : prouver qu'un langage n'est pas régulier. C'est un raisonnement par l'absurde, et le meilleur moyen de ne pas s'y perdre est de le voir comme un jeu à quatre coups, dont vous devez sortir gagnant :

1. L'adversaire suppose $L$ régulier et fournit la longueur $p$ (vous ne la connaissez pas).
2. Vous choisissez un mot $w \in L$ malin, avec $|w| \geq p$. C'est le coup décisif.
3. L'adversaire découpe $w = xyz$ comme il veut, en respectant $|xy| \leq p$ et $|y| \geq 1$.
4. Vous exhibez un $i$ tel que $xy^iz \notin L$ — contradiction.

Si vous gagnez quel que soit le découpage, $L$ n'est pas régulier. L'ordre des quantificateurs est tout : « pour tout $p$, il existe $w$, pour tout découpage, il existe $i$ ». Vous contrôlez $w$ et $i$ ; l'adversaire contrôle $p$ et le découpage.

Le cas $a^n b^n$

Appliquons le jeu à $L = \{a^n b^n \mid n \geq 0\}$ — le langage « autant de $a$ que de $b$, les $a$ avant les $b$ » que le chapitre 1 avait déjà isolé.

Le choix du mot est tout : on joue $w = a^p b^p$. Pourquoi celui-là ? Parce que la contrainte $|xy| \leq p$ oblige le bloc $xy$ à tomber entièrement dans la zone des $a$ — le mot commence par $p$ lettres $a$. Le facteur $y$ ne contient donc que des $a$, et il en contient au moins un.

Il suffit alors de pomper : prendre $i = 2$ donne $a^{p+k} b^p$ avec $k = |y| \geq 1$ — plus de $a$ que de $b$, donc hors de $L$. Contradiction. Comme ce raisonnement vaut pour n'importe quel découpage, $L$ n'est pas régulier.

La leçon générale dépasse cet exemple : un automate fini ne sait pas compter jusqu'à un nombre arbitraire. Reconnaître $a^n b^n$ exigerait de retenir $n$, qui n'est pas borné, alors que l'automate n'a qu'un nombre fini d'états. Le lemme de pompage est la traduction rigoureuse de cette limite — et c'est justement pour compter qu'on introduira, au chapitre 8, une mémoire supplémentaire : la pile.

À vous

L'exercice transforme le lemme en jeu jouable. L'adversaire annonce $p$ et essaie tous les découpages possibles ; vous devez fournir le mot $w = a^p b^p$ et le facteur pompé $i$ qui casse, et gagner contre chaque découpage.

C'est en jouant qu'on comprend pourquoi le choix du mot est décisif : c'est lui qui coince le facteur $y$ dans les $a$. Une fois cette mécanique vue tourner, le lemme de pompage cesse d'être un enchaînement de quantificateurs opaque et devient une stratégie que vous savez dérouler.

// On veut PROUVER que L = { a^n b^n | n >= 0 } n'est pas régulier.
//   L = { ε, ab, aabb, aaabbb, ... }  (autant de a que de b, a avant b)
//
// Le lemme de pompage, vu comme un JEU en 4 coups :
//   1. L'adversaire (qui affirme « L est régulier ») annonce une longueur p.
//   2. VOUS choisissez un mot w de L, avec |w| >= p.
//   3. L'adversaire découpe w = x y z avec |xy| <= p et |y| >= 1 (y non vide).
//   4. VOUS choisissez un entier i tel que x y^i z ne soit PAS dans L.
//   Si vous gagnez QUEL QUE SOIT le découpage, L n'est pas régulier.

// Appartenance à L : autant de a que de b, tous les a avant tous les b.
function estDansL(mot) {
  const m = mot.match(/^(a*)(b*)$/);          // a...a puis b...b
  if (!m) return false;                        // un b avant un a -> non
  return m[1].length === m[2].length;          // même nombre
}

// ── À VOUS (2) : choisir le bon mot ─────────────────────────────────────────
// Pour une longueur p donnée, quel mot de L rend l'adversaire perdant ?
// Indice : il faut que |xy| <= p FORCE y à ne contenir que des a.
function choisirMot(p) {
  return ""; // à compléter, en fonction de p
}

// ── À VOUS (4) : choisir i qui casse ────────────────────────────────────────
// Étant donné un découpage x, y, z (avec y = que des a, forcé par l'étape 2),
// rendez un i tel que x + y.repeat(i) + z ne soit PAS dans L.
function choisirI(x, y, z) {
  return 1; // à corriger (i = 1 redonne w, qui EST dans L : mauvais choix)
}

// ── Le jeu : l'adversaire essaie TOUS les découpages valides ────────────────
function jouer(p) {
  const w = choisirMot(p);
  if (w.length < p || !estDansL(w)) { console.log("Mot invalide."); return; }
  console.log("p = " + p + ", vous jouez w = " + w + " (dans L, |w| >= p)");
  let vousGagnezToujours = true;
  for (let coupe = 1; coupe <= p; coupe++) {       // |xy| <= p
    for (let ly = 1; coupe - ly >= 0 && ly <= coupe; ly++) {
      const x = w.slice(0, coupe - ly);
      const y = w.slice(coupe - ly, coupe);
      const z = w.slice(coupe);
      if (y.length < 1) continue;
      const i = choisirI(x, y, z);
      const pompe = x + y.repeat(i) + z;
      if (estDansL(pompe)) {
        console.log("  PERDU sur x=" + x + " y=" + y + " z=" + z + " : " + pompe + " est dans L");
        vousGagnezToujours = false;
      }
    }
  }
  console.log(vousGagnezToujours ? "GAGNÉ pour tout découpage -> L n'est pas régulier." : "à revoir");
}

jouer(3);
jouer(5);

function choisirMot(p) {
  // Le mot a^p b^p : sa longueur 2p >= p, et surtout comme |xy| <= p, le
  // bloc xy tombe ENTIÈREMENT dans les a. y ne contient donc que des a.
  return "a".repeat(p) + "b".repeat(p);
}

function choisirI(x, y, z) {
  // y = k a's (k >= 1). Pomper à i = 2 ajoute k a's SANS toucher aux b :
  // on obtient a^(p+k) b^p, qui a plus de a que de b -> hors de L.
  // (i = 0 marche aussi : a^(p-k) b^p, moins de a que de b.)
  return 2;
}

// jouer(3) et jouer(5) : GAGNÉ pour tout découpage -> L n'est pas régulier.
//
// ── Pourquoi ça marche, et pourquoi c'est LE raisonnement à retenir ─────────
//
// 1. Le choix du mot est le cœur de la preuve. En jouant a^p b^p, on exploite
//    la contrainte |xy| <= p : le facteur pompé y est COINCÉ dans la zone des
//    a. Pomper y déséquilibre alors le compte a/b, ce que L interdit. Un
//    mauvais choix de mot (ex. (ab)^p) laisserait l'adversaire s'en tirer.
//
// 2. C'est vous qui choisissez w et i ; l'adversaire choisit p et le découpage.
//    Vous devez gagner CONTRE TOUS ses choix — d'où la boucle qui teste tous
//    les découpages. La preuve est un « pour tout p, il existe w, pour tout
//    découpage, il existe i ».
//
// 3. L'intuition profonde : un automate fini a une MÉMOIRE BORNÉE (p états).
//    Pour reconnaître a^n b^n, il faudrait COMPTER les a jusqu'à un n
//    arbitraire, donc une mémoire non bornée. Le lemme de pompage est la
//    formalisation de « les automates finis ne savent pas compter ».
//
// 4. Portée : le lemme sert UNIQUEMENT à prouver qu'un langage N'EST PAS
//    régulier. Le vérifier ne prouve JAMAIS qu'un langage EST régulier — pour
//    ça, on exhibe un automate ou une expression régulière.

Ce que la suite en fait

Le bloc II est complet : vous savez décrire les langages réguliers de trois façons équivalentes, les optimiser, connaître leurs clôtures, et surtout prouver qu'un langage leur échappe. La frontière est tracée.

Le bloc III la franchit. Puisque les automates finis ne savent pas compter, on leur ajoute une mémoire : une pile. Le chapitre 7 introduit d'abord les grammaires hors contexte, une manière de engendrer les langages plutôt que de les reconnaître, capable justement de décrire $a^n b^n$ ; le chapitre 8 leur associe les automates à pile, et donnera un lemme de pompage algébrique qui tracera, un cran plus haut, la frontière suivante.

À retenir

Exercices d'entraînement