Mots et langages

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));
}

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