Propriétés et limites

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