Un compilateur, un moteur de recherche, un validateur de formulaire, un correcteur orthographique : tous partagent une même question, posée des milliards de fois par seconde. Une suite de caractères appartient-elle à un ensemble décrit à l'avance — les programmes C corrects, les adresses de courriel valides, les nombres bien formés ?

Répondre à cette question, c'est tout le cours. Mais avant de décider si un mot appartient à un langage, il faut définir avec une précision totale ce qu'est un mot, ce qu'est un langage, et ce qu'on a le droit d'en faire. Ce premier chapitre pose ce vocabulaire. Il paraît élémentaire ; il ne l'est pas, et la moitié des erreurs de l'année viennent d'une définition mal assimilée ici — en particulier celle du mot vide.

Alphabet, mot, longueur

Un alphabet, noté $\Sigma$, est un ensemble fini et non vide de symboles. Ce ne sont pas forcément des lettres : $\Sigma = \{a, b\}$, $\Sigma = \{0, 1\}$, l'ensemble des caractères ASCII, ou même un ensemble de mots entiers d'un langage de programmation traités comme des symboles uniques.

Un mot (ou chaîne) sur $\Sigma$ est une suite finie de symboles de $\Sigma$. Sur $\Sigma = \{a, b\}$, abba et aaa sont des mots ; abc n'en est pas un, car c n'appartient pas à l'alphabet.

La longueur d'un mot $u$, notée $|u|$, est le nombre de symboles qui le composent : $|abba| = 4$. On peut aussi compter les occurrences d'un symbole donné : $|abba|_a = 2$.

Le cas particulier qui décide de tout : le mot vide, noté $\varepsilon$. C'est le mot de longueur zéro, $|\varepsilon| = 0$. Trois pièges à désamorcer immédiatement :

• $\varepsilon$ est un mot, au même titre que les autres. « De longueur nulle » ne veut pas dire « inexistant ».
• $\varepsilon \neq \emptyset$. Le mot vide est un objet ; l'ensemble vide est un ensemble sans aucun élément. Confondre les deux est l'erreur la plus fréquente du cours.
• $\varepsilon$ n'est pas le symbole espace. Un espace est un symbole de longueur 1 comme un autre.

Préfixe, suffixe, facteur

Trois façons de « prendre un morceau » d'un mot $w$ :

Remarquez que $\varepsilon$ et $w$ lui-même sont toujours à la fois préfixe, suffixe et facteur de $w$. Ce ne sont pas des cas dégénérés qu'on écarte : les définitions les incluent, et les preuves du cours s'appuient sur cette inclusion.

La concaténation

L'opération de base sur les mots est la concaténation : mettre bout à bout. On la note par un point, souvent omis :

$u \cdot v = uv \qquad \text{par exemple} \quad ab \cdot ba = abba.$

Deux propriétés structurent tout le reste, et méritent d'être énoncées comme telles.

Elle est associative : $(u \cdot v) \cdot w = u \cdot (v \cdot w)$. On peut donc écrire $uvw$ sans parenthèses.

Elle admet un élément neutre, et c'est $\varepsilon$ : $u \cdot \varepsilon = \varepsilon \cdot u = u$. C'est ici que le mot vide gagne son utilité — il joue pour la concaténation le rôle que zéro joue pour l'addition. Sans lui, la théorie serait pleine de cas particuliers.

En revanche, la concaténation n'est pas commutative : $ab \neq ba$ en général. L'ordre des symboles est l'information portée par un mot.

Enfin, les longueurs s'ajoutent : $|u \cdot v| = |u| + |v|$. Cette égalité si simple est la clé des preuves par récurrence sur la longueur du chapitre suivant.

Σ* : l'ensemble de tous les mots

On note $\Sigma^*$ l'ensemble de tous les mots que l'on peut former sur $\Sigma$, y compris $\varepsilon$. C'est le terrain de jeu du cours entier.

$\Sigma^*$ est infini — il n'y a pas de mot le plus long — mais il est dénombrable : on peut énumérer ses éléments sans en oublier aucun, en les rangeant par longueur croissante. Sur $\Sigma = \{a, b\}$ :

1longueur 0 : ε2longueur 1 : a, b3longueur 2 : aa, ab, ba, bb4longueur 3 : aaa, aab, aba, abb, baa, bab, bba, bbb5...

Le comptage suit une logique simple : chaque mot de longueur $n$ s'obtient en plaçant l'une des $|\Sigma|$ lettres devant un mot de longueur $n-1$. Il y a donc exactement $|\Sigma|^n$ mots de longueur $n$ — 1, 2, 4, 8 sur un alphabet de deux lettres, comme dans la liste ci-dessus. Vous retrouverez cette formule par vous-même dans l'exercice, en la construisant plutôt qu'en la récitant.

Un langage est un ensemble de mots

Voici la définition centrale, et elle est d'une simplicité désarmante :

Un langage $L$ sur $\Sigma$ est un sous-ensemble de $\Sigma^*$, c'est-à-dire $L \subseteq \Sigma^*$.

Rien de plus. Un langage est un ensemble de mots — fini ou infini. Quelques exemples sur $\Sigma = \{a, b\}$ :

• $L_1 = \{a, ab, abb\}$ — un langage fini de trois mots ;
• $L_2 = \{\varepsilon\}$ — le langage qui ne contient que le mot vide (un élément) ;
• $L_3 = \emptyset$ — le langage vide, aucun mot ;
• $L_4 = \{a^n b^n \mid n \geq 0\} = \{\varepsilon, ab, aabb, aaabb b, \dots\}$ — un langage infini, qui reviendra hanter le chapitre 6 ;
• $L_5$ = « tous les mots qui contiennent le facteur aa » — infini lui aussi.

Notez encore la distinction, cruciale et régulièrement ratée en examen : $\{\varepsilon\}$ et $\emptyset$ sont deux langages différents. Le premier contient un mot (le mot vide) ; le second n'en contient aucun. C'est la même différence qu'entre une boîte contenant une feuille blanche et une boîte vide.

Les opérations sur les langages

Comme les langages sont des ensembles, on hérite des opérations ensemblistes, plus deux opérations propres aux mots.

L'union $L_1 \cup L_2$, l'intersection $L_1 \cap L_2$ et le complément $\overline{L} = \Sigma^* \setminus L$ sont les opérations ensemblistes habituelles.

La concaténation de langages étend celle des mots à tout l'ensemble :

$L_1 \cdot L_2 = \{\, u \cdot v \mid u \in L_1,\ v \in L_2 \,\}.$

On prend chaque mot du premier, chaque mot du second, on les colle. Si $L_1 = \{a, ab\}$ et $L_2 = \{b, c\}$, alors $L_1 \cdot L_2 = \{ab, ac, abb, abc\}$.

Enfin, l'opération reine de la théorie, l'étoile de Kleene :

$L^* = \{\varepsilon\} \cup L \cup L^2 \cup L^3 \cup \cdots$

où $L^n$ est la concaténation de $L$ avec lui-même $n$ fois. Autrement dit, $L^*$ contient tous les mots obtenus en concaténant zéro, un ou plusieurs mots de $L$. Le « zéro » est capital : $\varepsilon \in L^*$ toujours, même si $\varepsilon \notin L$. C'est encore le mot vide qui se glisse dans la définition, et l'oublier fausse la moitié des exercices sur les expressions régulières du chapitre 5. La notation $\Sigma^*$ que vous employez depuis le début n'est d'ailleurs rien d'autre que l'étoile de Kleene appliquée à l'alphabet vu comme un langage de mots d'une lettre.

À vous

L'exercice est votre premier contact avec ces objets, en code. Vous implémentez les opérations de base — longueur, concaténation, préfixe — puis vous énumérez tous les mots de longueur $n$ sur un alphabet donné, et vous vérifiez que leur nombre vaut bien $|\Sigma|^n$.

Le but n'est pas la programmation mais la définition : en écrivant concatener(u, ε), on comprend une fois pour toutes pourquoi $\varepsilon$ est l'élément neutre, et en comptant les mots, on construit la formule au lieu de l'apprendre.

// Un mot est une suite finie de symboles pris dans un alphabet. En code, on
// le représente par une chaîne, et l'alphabet par un tableau de symboles.
const SIGMA = ["a", "b"];        // alphabet à 2 lettres
const MOT_VIDE = "";             // le mot vide, noté ε en cours (longueur 0)

// ── À VOUS (1) : les opérations de base ─────────────────────────────────────
function longueur(u) {
  return 0; // à compléter
}
function concatener(u, v) {
  return ""; // à compléter — attention : concatener(u, MOT_VIDE) doit rendre u
}
function estPrefixe(u, w) {
  // u est-il un préfixe de w ? (w commence-t-il par u ?)
  return false; // à compléter
}

// ── À VOUS (2) : dénombrer ──────────────────────────────────────────────────
// motsDeLongueur(n) doit rendre TOUS les mots de longueur n sur SIGMA.
// Combien y en a-t-il ? Vérifiez que |resultat| = |SIGMA|^n.
function motsDeLongueur(n) {
  return []; // à compléter (récursion ou boucle)
}

// ── Vérification ────────────────────────────────────────────────────────────
console.log("longueur('abba') =", longueur("abba"), "(attendu 4)");
console.log("concatener('ab','ba') =", concatener("ab", "ba"), "(attendu abba)");
console.log("concatener('ab', ε) =", "'" + concatener("ab", MOT_VIDE) + "'", "(attendu ab)");
console.log("estPrefixe('ab','abba') =", estPrefixe("ab", "abba"), "(attendu true)");
console.log("");
for (let n = 0; n <= 3; n++) {
  const m = motsDeLongueur(n);
  console.log("mots de longueur " + n + " : " + m.length + " -> [" + m.join(", ") + "]");
  console.log("   |SIGMA|^" + n + " = " + Math.pow(SIGMA.length, n));
}

function longueur(u) {
  return u.length;
}
function concatener(u, v) {
  return u + v;              // le mot vide est l'élément neutre : u·ε = ε·u = u
}
function estPrefixe(u, w) {
  return w.slice(0, u.length) === u;
}

function motsDeLongueur(n) {
  if (n === 0) return [MOT_VIDE];              // un seul mot de longueur 0 : ε
  const petits = motsDeLongueur(n - 1);        // les mots de longueur n-1
  const resultat = [];
  for (const m of petits)                      // devant chacun,
    for (const lettre of SIGMA)                // on place chaque lettre
      resultat.push(lettre + m);
  return resultat;
}

// ── Ce que l'exercice montre ────────────────────────────────────────────────
//
// 1. Le mot vide ε n'est PAS "rien" : c'est un mot, de longueur 0, et il est
//    l'élément neutre de la concaténation (u·ε = u). L'oublier fausse
//    récurrences et automates — la moitié des erreurs du cours viennent de là.
//
// 2. Le dénombrement suit une récurrence : chaque mot de longueur n s'obtient
//    en ajoutant UNE des |SIGMA| lettres devant un mot de longueur n-1. D'où
//        (nb de longueur n) = |SIGMA| × (nb de longueur n-1),  avec 1 pour n=0.
//    La solution de cette récurrence est |SIGMA|^n. On ne l'a pas récitée :
//    on l'a construite, et le code la vérifie (1, 2, 4, 8 sur un alphabet de 2).
//
// 3. Σ* — l'ensemble de TOUS les mots — est donc infini, mais DÉNOMBRABLE :
//    on peut les énumérer longueur par longueur, sans en oublier aucun. C'est
//    la première brique de tout le cours : un langage sera un sous-ensemble
//    de ce Σ*.

Ce que la suite en fait

Ce vocabulaire est le socle de tout. Le chapitre 2 se dote des outils pour prouver des propriétés sur ces objets — l'induction et la récurrence sur la longueur d'un mot, qui reposent directement sur l'égalité $|uv| = |u| + |v|$ vue ici.

Ensuite, tout le cours consistera à décrire des langages — d'abord les plus simples, les langages réguliers, par des automates (chapitre 3) et des expressions régulières (chapitre 5) — et à comprendre ce que chaque outil peut et ne peut pas décrire. La question « ce mot appartient-il à ce langage ? » de l'introduction ne vous quittera plus.

À retenir

Exercices d'entraînement

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