Rappels mathématiques utiles

Le chapitre 1 a défini les objets ; celui-ci fournit les outils pour raisonner dessus. Ce ne sont pas des rappels décoratifs : sans induction ni récurrence, on ne peut prouver aucun théorème du cours, et sans la notion de fonction, on ne peut pas définir un automate. Ce chapitre est court parce qu'il suppose des bases acquises — mais il isole précisément les points que la théorie des langages sollicite sans cesse, et où l'imprécision se paie plus tard.

Ensembles, un rappel ciblé

Un langage est un ensemble ; les opérations du chapitre 1 sont des opérations d'ensembles. Trois points méritent d'être fixés, parce qu'ils reviendront tels quels.

L'inclusion $A \subseteq B$ signifie : tout élément de $A$ est élément de $B$. Pour prouver $A \subseteq B$, on prend un élément quelconque de $A$ et on montre qu'il est dans $B$. Pour prouver une égalité $A = B$, la méthode standard est la double inclusion : $A \subseteq B$ et $B \subseteq A$. C'est ainsi qu'on démontrera l'équivalence de deux automates, ou d'un automate et d'une expression régulière.

Le cardinal $|A|$ est le nombre d'éléments de $A$. Un ensemble peut être fini, infini dénombrable (ses éléments peuvent être énumérés en liste, comme $\Sigma^*$) ou non dénombrable. Cette distinction n'est pas anodine : elle est la clé d'un résultat surprenant vu plus bas.

L'ensemble des parties $\mathcal{P}(A)$ est l'ensemble de tous les sous-ensembles de $A$. Si $A$ a $n$ éléments, $\mathcal{P}(A)$ en a $2^n$. Retenez ce $2^n$ : il expliquera, au chapitre 4, pourquoi la déterminisation d'un automate peut faire exploser son nombre d'états.

Relations

Une relation sur un ensemble $E$ est un sous-ensemble de $E \times E$ : elle dit quels couples sont « en relation ». Une relation peut être réflexive, symétrique, transitive.

Le cas important pour le cours est la relation d'équivalence : réflexive, symétrique et transitive à la fois. Une telle relation partitionne $E$ en classes d'équivalence — des paquets disjoints qui recouvrent tout $E$, où deux éléments sont dans le même paquet exactement quand ils sont en relation. Cette idée, abstraite pour l'instant, sera l'outil exact de la minimisation d'un automate au chapitre 6 : on regroupera les états « indistinguables » en une seule classe.

L'induction structurelle

Beaucoup d'objets du cours sont définis inductivement : on donne des cas de base, puis des règles pour construire des objets plus gros à partir d'objets plus petits. Le mot lui-même se définit ainsi :

• base : $\varepsilon$ est un mot ;
• règle : si $u$ est un mot et $a \in \Sigma$ une lettre, alors $a \cdot u$ est un mot.

Tout mot s'obtient par un nombre fini d'applications de la règle à partir de la base. Les expressions régulières (chapitre 5) et les grammaires (chapitre 7) sont définies exactement de la même manière.

Quand un objet est défini inductivement, on le raisonne par induction structurelle : pour prouver qu'une propriété $P$ vaut pour tous les objets, il suffit de la prouver sur les cas de base, puis de montrer qu'elle se transmet par chaque règle de construction. C'est le même principe que la récurrence sur les entiers, appliqué à la structure de l'objet plutôt qu'à un nombre.

La récurrence sur la longueur d'un mot

C'est le schéma de preuve le plus employé du cours, et celui de l'exercice. Pour établir qu'une propriété $P(u)$ est vraie pour tout mot $u$, on procède par récurrence sur $|u|$ :

1. Base : on prouve $P(\varepsilon)$ — la propriété pour le mot vide, de longueur 0.
2. Hérédité : on suppose $P$ vraie pour tout mot de longueur $n$ (hypothèse de récurrence), et on en déduit $P$ pour un mot quelconque de longueur $n+1$, généralement écrit $u = a \cdot w$ avec $|w| = n$.

Comme tout mot a une longueur finie, ces deux étapes suffisent à couvrir $\Sigma^*$ tout entier. L'égalité $|u \cdot v| = |u| + |v|$ du chapitre 1 est l'ingrédient qui fait fonctionner presque toutes ces récurrences.

Un point de méthode qui sépare les copies : le cas de base ne se néglige jamais. Oublier de traiter $\varepsilon$ — parce qu'il « paraît évident » — est l'erreur classique, et souvent c'est précisément là que la propriété est la plus subtile à établir.

La fonction de transition

Dernier outil, et le plus tourné vers la suite. Une fonction $f : A \to B$ associe à chaque élément de $A$ (le domaine) un élément de $B$ (le codomaine). « Un », pas « au moins un » ni « au plus un » : à chaque entrée correspond exactement une sortie.

L'objet central du cœur du cours est la fonction de transition d'un automate, qu'on notera $\delta$. Elle prendra un état et une lettre, et rendra un état :

$\delta : Q \times \Sigma \to Q, \qquad \delta(q, a) = q'.$

Lue à voix haute : « depuis l'état $q$, en lisant la lettre $a$, on va dans l'état $q'$ ». Toute la mécanique d'un automate déterministe (chapitre 3) tiendra dans cette fonction. Et c'est justement l'exigence de fonction — une seule sortie par entrée — qui distinguera le déterminisme du non-déterminisme : au chapitre 4, on relâchera cette contrainte, $\delta$ rendra un ensemble d'états, et l'on ne parlera plus de fonction au sens strict mais de relation. Toute la difficulté de la déterminisation viendra de ce basculement.

À vous

L'exercice met la récurrence en pratique sur un objet concret : le miroir d'un mot. Vous définissez la fonction miroir par récursion sur la structure du mot — un cas de base pour $\varepsilon$, un cas récursif pour $a \cdot w$ —, puis vous testez la propriété $\text{miroir}(u \cdot v) = \text{miroir}(v) \cdot \text{miroir}(u)$.

L'important est ce que la solution révèle : la structure de la fonction récursive est exactement celle de la preuve par récurrence. Définir par récursion et prouver par récurrence sont le même geste — celui que vous répéterez tout le reste de l'année.

// Le miroir d'un mot : miroir(abc) = cba. On le définit PAR RÉCURSION sur la
// structure du mot — exactement comme on le prouverait par induction.
//
//   miroir(ε)      = ε                      (cas de base)
//   miroir(a · u)  = miroir(u) · a          (cas récursif : a est la 1re lettre)
//
// C'est la traduction en code d'une définition inductive. Le "cas de base" et
// le "cas récursif" sont exactement les deux cas d'une preuve par récurrence.

// ── À VOUS (1) : définir miroir par récursion ───────────────────────────────
function miroir(u) {
  if (u === "") return "";        // cas de base : miroir(ε) = ε
  // cas récursif : première lettre = u[0], reste = u.slice(1)
  return ""; // à compléter avec miroir(u.slice(1)) et u[0]
}

// ── À VOUS (2) : vérifier une propriété par la pratique ─────────────────────
// PROPRIÉTÉ à établir : pour tous mots u, v :  miroir(u·v) = miroir(v)·miroir(u)
// (l'ordre s'inverse !). Testez-la sur de nombreux couples : si elle tient
// partout, c'est bon signe — mais SEULE une preuve par récurrence la garantit.
function proprieteTient(u, v) {
  return miroir(u + v) === miroir(v) + miroir(u);
}

// ── Vérification ────────────────────────────────────────────────────────────
console.log("miroir('abc') =", miroir("abc"), "(attendu cba)");
console.log("miroir('') =", "'" + miroir("") + "'", "(attendu ε)");
console.log("");
const mots = ["", "a", "ab", "abba", "aabb", "xyz"];
let toutesOk = true;
for (const u of mots) for (const v of mots) {
  if (!proprieteTient(u, v)) { console.log("CONTRE-EXEMPLE : u=" + u + " v=" + v); toutesOk = false; }
}
console.log(toutesOk ? "La propriété tient sur tous les tests." : "Propriété fausse !");

function miroir(u) {
  if (u === "") return "";
  return miroir(u.slice(1)) + u[0];   // on renvoie le miroir du reste, PUIS
                                       // la première lettre — qui passe au bout
}

// La propriété miroir(u·v) = miroir(v)·miroir(u) tient sur tous les tests.
// Les tests NE la prouvent PAS — ils ne couvrent qu'un nombre fini de cas.
// Voici la preuve, qui est le vrai objet du chapitre :
//
// ── Preuve par récurrence sur |u| ──────────────────────────────────────────
//
// On veut : ∀u ∀v, miroir(u·v) = miroir(v)·miroir(u).
// On raisonne par récurrence sur la longueur de u.
//
// BASE (|u| = 0, donc u = ε) :
//     miroir(ε·v) = miroir(v)              car ε·v = v
//                 = miroir(v)·ε            car ε est neutre
//                 = miroir(v)·miroir(ε)    car miroir(ε) = ε
//     ✓ la propriété est vraie pour u = ε.
//
// HÉRÉDITÉ : supposons la propriété vraie pour tout mot de longueur n
// (hypothèse de récurrence). Soit u de longueur n+1 ; on l'écrit u = a·w
// avec a une lettre et |w| = n. Alors :
//     miroir(u·v)   = miroir(a·w·v)
//                   = miroir(w·v)·a           (définition de miroir)
//                   = (miroir(v)·miroir(w))·a (hypothèse de récurrence sur w)
//                   = miroir(v)·(miroir(w)·a) (associativité)
//                   = miroir(v)·miroir(a·w)   (définition de miroir, à rebours)
//                   = miroir(v)·miroir(u).
//     ✓ la propriété se transmet de n à n+1.
//
// Par le principe de récurrence, elle est vraie pour TOUT u. CQFD.
//
// ── Ce qu'il faut retenir ───────────────────────────────────────────────────
// La STRUCTURE de la fonction récursive (cas de base ε, cas récursif a·w) est
// exactement la structure de la preuve (base ε, hérédité de w à a·w). Définir
// par récursion et prouver par récurrence, c'est le même geste. C'est le
// schéma de raisonnement de TOUT le cours — les automates, Kleene, le lemme
// de pompage s'en servent tous.

Ce que la suite en fait

Vous disposez maintenant du vocabulaire (chapitre 1) et des outils de preuve (ce chapitre). Le bloc II peut commencer, et c'est le cœur du cours.

Le chapitre 3 introduit l'objet vers lequel tout ce qui précède tendait : l'automate fini déterministe, entièrement bâti sur la fonction de transition $\delta$ définie ici. La double inclusion servira à prouver des équivalences, la récurrence sur la longueur à établir qu'un automate reconnaît bien le langage voulu, et le $2^n$ de l'ensemble des parties reviendra dès le chapitre 4 pour expliquer le coût de la déterminisation.

À retenir

Exercices d'entraînement