Automates à pile

Le chapitre 7 a montré comment engendrer les langages algébriques avec des grammaires. Il manque la contrepartie que le bloc II avait pour les réguliers : la machine qui les reconnaît. Le chapitre 6 avait diagnostiqué le manque avec précision — un automate fini ne sait pas compter, faute de mémoire non bornée. La solution est d'ajouter cette mémoire, sous une forme très particulière : une pile.

Ce choix n'est pas arbitraire. Une pile — dernier entré, premier sorti — est exactement ce qu'il faut pour apparier des symboles de part et d'autre : empiler à l'aller, dépiler au retour. C'est le mécanisme qui vérifie que les parenthèses d'un programme sont bien équilibrées, et c'est la même idée qui reconnaît $a^n b^n$.

L'automate à pile

Un automate à pile est un automate fini augmenté d'une pile de capacité illimitée. À chaque transition, il peut désormais :

• lire une lettre de l'entrée (ou $\varepsilon$, sans rien lire) ;
• consulter et dépiler le symbole au sommet de la pile ;
• empiler de nouveaux symboles.

La transition dépend donc de trois choses — l'état, la lettre lue, le sommet de la pile — et agit sur deux — l'état et la pile. La contrainte essentielle, celle qui définit le modèle et fixe sa puissance, est que l'automate n'accède qu'au sommet : il ne voit ni ne modifie le reste de la pile. Il travaille sur une mémoire non bornée, mais d'accès strictement discipliné.

L'intuition à garder : la hauteur de la pile est un compteur. Pour $a^n b^n$, on empile un jeton à chaque $a$ et on en dépile un à chaque $b$. La pile monte pendant les $a$, redescend pendant les $b$, et se retrouve vide exactement quand les deux nombres sont égaux. Ce compteur peut grimper aussi haut qu'on veut — c'est précisément la mémoire non bornée que les états finis ne pouvaient offrir.

Deux critères d'acceptation

Un automate à pile peut décider d'accepter de deux manières, et il faut connaître les deux :

• par pile vide : le mot est accepté si, après l'avoir entièrement lu, la pile est vide ;
• par état final : le mot est accepté si la lecture se termine dans un état acceptant, quelle que soit la pile.

Ces deux critères sont équivalents : tout langage reconnu par pile vide l'est aussi par état final, et réciproquement, quitte à transformer l'automate. On choisit celui qui rend la construction la plus naturelle. Pour $a^n b^n$, l'acceptation par pile vide est la plus directe — « autant de $b$ que de $a$ » se traduit littéralement par « la pile est retombée à vide » —, et c'est celle de l'exercice.

L'équivalence avec les grammaires

Voici le résultat central du chapitre, l'analogue du théorème de Kleene un étage plus haut :

Les automates à pile reconnaissent exactement les langages engendrés par les grammaires hors contexte.

Grammaire et automate à pile sont donc deux visages du même objet : le premier engendre, le second reconnaît, la même classe des langages algébriques. On peut transformer effectivement l'un en l'autre — d'une grammaire, on construit un automate à pile qui simule ses dérivations sur la pile ; d'un automate à pile, on extrait une grammaire.

Une différence capitale avec le bloc II mérite d'être soulignée, car elle prend à contre-pied l'intuition acquise au chapitre 4. Là, déterministe et non déterministe étaient équivalents. Ici, ce n'est plus vrai : les automates à pile non déterministes sont strictement plus puissants que les déterministes. Certains langages algébriques n'ont pas d'automate à pile déterministe. C'est le non-déterminisme qui donne toute sa force au modèle — et c'est aussi ce qui rend l'analyse syntaxique générale (chapitre 9) plus délicate que l'analyse lexicale, laquelle reste dans le monde déterministe des automates finis.

Le lemme de pompage algébrique

Ayant élargi la classe, on retrouve la question du chapitre 6 : y a-t-il des langages qui échappent même aux grammaires hors contexte ? Oui — et l'outil pour le prouver est un lemme de pompage algébrique, cousin de celui des réguliers.

L'idée est la même — un objet fini forcé de se répéter sur une entrée assez longue — mais un arbre de dérivation profond doit réutiliser une variable sur un chemin, ce qui crée deux zones pompables simultanément au lieu d'une. Le lemme s'énonce donc avec une décomposition en cinq morceaux : tout mot assez long $w \in L$ s'écrit $w = uvxyz$ avec $vy$ non vide, $|vxy|$ borné, et $uv^ixy^iz \in L$ pour tout $i \geq 0$. On pompe $v$ et $y$ ensemble.

L'usage est identique à celui du chapitre 6 : prouver qu'un langage n'est pas algébrique. Le cas d'école est $a^n b^n c^n$ — trois familles à équilibrer en même temps. Une pile sait apparier deux familles ($a$ contre $b$), mais elle n'a qu'un sommet : elle ne peut pas suivre simultanément un troisième compte. Le pompage à deux zones fait précisément apparaître ce déséquilibre, et prouve que $a^n b^n c^n$ dépasse les automates à pile.

On retrouve ainsi, un cran plus haut, exactement la structure du bloc II : un modèle de machine, une classe de langages, et un lemme de pompage qui en marque la frontière — au-dessus commencent les langages contextuels, puis la machine de Turing.

À vous

L'exercice rend tangible l'idée maîtresse du chapitre : la pile permet de compter. Vous implémentez le moteur d'un automate à pile qui reconnaît $a^n b^n$ par pile vide — empiler un jeton par $a$, dépiler un par $b$, accepter si la pile finit vide — et vous voyez la hauteur de la pile monter puis redescendre.

C'est ce compteur non borné, impossible avec un nombre fini d'états, qui fait basculer des langages réguliers aux langages algébriques. En le codant, vous touchez du doigt à la fois la puissance du modèle (il compte) et sa limite (il n'a qu'un sommet, d'où $a^n b^n c^n$ hors d'atteinte).

// Un automate à pile = un automate fini + une PILE. C'est la pile qui donne
// la mémoire non bornée qui manquait au chapitre 6.
//
// Idée pour L = { a^n b^n } : EMPILER un jeton à chaque 'a', DÉPILER un jeton
// à chaque 'b'. Si la pile est vide à la fin (et qu'on n'a jamais dépilé à
// vide, ni lu un a après un b), alors il y avait autant de b que de a.
// Acceptation PAR PILE VIDE.

// ── À VOUS : le moteur de reconnaissance ────────────────────────────────────
function accepte(mot) {
  const pile = [];
  let phase = "a";              // on lit d'abord des a, puis des b
  for (const c of mot) {
    if (c === "a") {
      // à compléter : on ne doit plus lire de a une fois en phase b
      // puis empiler un jeton
    } else if (c === "b") {
      // à compléter : passer en phase b ; dépiler un jeton ;
      // si la pile est déjà vide -> trop de b -> rejet
    } else {
      return false;            // symbole hors alphabet
    }
  }
  // à compléter : accepté si la pile est VIDE à la fin
  return false;
}

// ── Vérification ────────────────────────────────────────────────────────────
const tests = [
  ["",       true],    // n = 0
  ["ab",     true],    // n = 1
  ["aabb",   true],    // n = 2
  ["aaabbb", true],    // n = 3
  ["aab",    false],   // 2 a, 1 b
  ["abb",    false],   // 1 a, 2 b
  ["ba",     false],   // b avant a
  ["abab",   false],   // pas de la forme a...a b...b
];
for (const [mot, attendu] of tests) {
  const r = accepte(mot);
  console.log("'" + mot + "'".padEnd(8) + " -> " + r + (r === attendu ? "  ok" : "  ✗"));
}

function accepte(mot) {
  const pile = [];
  let phase = "a";
  for (const c of mot) {
    if (c === "a") {
      if (phase === "b") return false;   // un a après un b : forme interdite
      pile.push("X");                    // EMPILER : un jeton par a
    } else if (c === "b") {
      phase = "b";
      if (pile.length === 0) return false; // DÉPILER à vide : trop de b
      pile.pop();                          // DÉPILER : un jeton par b
    } else {
      return false;
    }
  }
  return pile.length === 0;               // pile vide <=> autant de b que de a
}

// ── Ce que l'exercice enseigne ──────────────────────────────────────────────
//
// 1. La PILE est la mémoire qui manquait. La hauteur de la pile compte les a
//    non encore appariés — elle peut monter aussi haut qu'on veut, ce qu'un
//    nombre FINI d'états ne pouvait pas faire (chapitre 6). C'est très
//    exactement ce qui fait passer des langages réguliers aux algébriques.
//
// 2. On n'accède qu'au SOMMET de la pile — c'est la contrainte du modèle, et
//    sa limite. On peut apparier a et b (a^n b^n), mais on ne peut pas
//    apparier TROIS familles à la fois : a^n b^n c^n échappe même aux
//    automates à pile (lemme de pompage algébrique, plus bas dans le cours).
//
// 3. Deux critères d'acceptation existent et sont équivalents :
//    - par PILE VIDE (utilisé ici) ;
//    - par ÉTAT FINAL (on accepte si on finit dans un état acceptant).
//    On passe de l'un à l'autre sans changer la classe de langages reconnus.
//
// 4. Équivalence fondamentale : les automates à pile (NON déterministes)
//    reconnaissent EXACTEMENT les langages engendrés par les grammaires hors
//    contexte (chapitre 7). C'est l'analogue du théorème de Kleene, un étage
//    plus haut. Attention : contrairement aux automates finis, les automates
//    à pile déterministes sont STRICTEMENT moins puissants que les non
//    déterministes.

Ce que la suite en fait

Le bloc III est complet : grammaires pour engendrer, automates à pile pour reconnaître, reliés par une équivalence, et un lemme de pompage pour en marquer la limite. Vous avez maintenant deux étages de la hiérarchie de Chomsky, chacun avec sa machine, sa notation et sa frontière.

Le bloc IV quitte la théorie pure pour l'application qui lui donne tout son sens. Le chapitre 9 montre comment ces deux étages travaillent ensemble dans un compilateur : les langages réguliers (automates finis, chapitres 3 à 6) découpent le texte source en unités lexicales, et les langages algébriques (grammaires, ce bloc) en reconstruisent la structure. Toute la théorie du cours converge là.

À retenir

Exercices d'entraînement