Expressions régulières

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