Automates non déterministes

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