Mots et langages

Pourquoi des langages

Un compilateur commence par lire un texte : il faut décider si x1 est un identifiant, si 0x1F est un nombre, si if (a) b; else c; est une instruction. Un moteur de recherche filtre les lignes qui contiennent une adresse électronique. Un protocole réseau vérifie qu'un message a la bonne forme. Dans tous ces cas, la question est la même : ce mot appartient-il à cet ensemble de mots ?

Ce cours étudie la famille d'ensembles de mots la plus simple qui soit utile : les langages rationnels. On les décrit de deux façons, qu'on apprendra à traduire l'une dans l'autre :

• par des expressions rationnelles, faites pour être écrites et lues par des humains (chapitre 2) ;
• par des automates finis, faits pour être exécutés par des machines (chapitre 3).

Avant cela, il faut fixer le vocabulaire : c'est l'objet de ce chapitre.

Les mots

Alphabet et mot

Les « lettres » ne sont pas forcément des caractères. Selon ce qu'on étudie, $\Sigma$ peut être :

• $\{a, b\}$, pour les exemples de ce cours ;
• $\{0, 1\}$, pour les nombres binaires ;
• les 128 caractères ASCII, pour un analyseur de texte ;
• $\{\texttt{if}, \texttt{else}, \texttt{id}, \texttt{(}, \texttt{)}, \texttt{;}\}$, pour un analyseur syntaxique qui reçoit des mots-clés déjà reconnus.

Ce qui compte, c'est que l'alphabet soit fini. Les mots, eux, sont en nombre infini, mais chacun est fini.

Longueur

La longueur d'un mot $u$, notée $|u|$, est son nombre de lettres : $|abba| = 4$, $|\varepsilon| = 0$. Pour une lettre $a$, on note $|u|_a$ le nombre d'occurrences de $a$ dans $u$ : $|abba|_a = 2$, $|abba|_b = 2$.

Il y a $|\Sigma|^n$ mots de longueur $n$ sur $\Sigma$ : pour chacune des $n$ positions, on choisit une lettre parmi $|\Sigma|$. Sur $\{a, b\}$, il y a un mot de longueur 0, deux de longueur 1, quatre de longueur 2, huit de longueur 3.

Concaténation

Avec $u = ab$ et $v = ba$ : $uv = abba$ et $vu = baab$. La concaténation a trois propriétés à connaître :

• elle est associative : $(uv)w = u(vw)$, ce qui permet d'écrire $uvw$ sans parenthèses ;
• $\varepsilon$ en est l'élément neutre : $u\varepsilon = \varepsilon u = u$ ;
• elle n'est pas commutative : $uv \neq vu$ en général, comme on vient de le voir.

Et les longueurs s'additionnent : $|uv| = |u| + |v|$.

On note $u^n$ le mot $u$ répété $n$ fois : $u^0 = \varepsilon$, et $u^{n+1} = u^n u$. Ainsi $(ab)^3 = ababab$, qu'il ne faut pas confondre avec $ab^3 = abbb$ : l'exposant porte sur ce qui le précède immédiatement.

Préfixes, suffixes, facteurs

Un préfixe est un facteur avec $w_1 = \varepsilon$, un suffixe un facteur avec $w_2 = \varepsilon$. Tout mot est préfixe, suffixe et facteur de lui-même, et $\varepsilon$ est préfixe, suffixe et facteur de tout mot.

Sous-mots

$ac$ est un sous-mot de $abc$, mais pas un facteur. Tout facteur est un sous-mot ; la réciproque est fausse.

Le transposé

Le transposé (ou miroir) de $u$, noté $u^t$ (parfois $\tilde{u}$), est le mot $u$ écrit à l'envers : $(abb)^t = bba$. On a $(uv)^t = v^t u^t$ : l'ordre s'inverse, comme pour la transposée d'un produit de matrices. Un mot égal à son transposé est un palindrome : $abba$, $aba$, $\varepsilon$.

Les langages

Définition

Un langage peut être fini ou infini, et il n'a aucune raison d'être « régulier » au sens courant du terme.

Opérations ensemblistes

Un langage étant un ensemble, on dispose des opérations ensemblistes : union $L_1 \cup L_2$, intersection $L_1 \cap L_2$, différence $L_1 \setminus L_2$, complémentaire $\overline{L} = \Sigma^* \setminus L$.

Avec les langages de l'exemple : $L_2 \cap L_3$ contient les mots qui commencent par $a$ et ont autant de $a$ que de $b$ ; $\overline{L_2}$ contient $\varepsilon$ et les mots qui commencent par $b$. Le complémentaire dépend de l'alphabet : il faut toujours savoir quel est $\Sigma$.

Produit de langages

Le produit hérite des propriétés de la concaténation : il est associatif, $\{\varepsilon\}$ en est l'élément neutre, et il n'est pas commutatif ($\{a\}\{b\} = \{ab\}$, $\{b\}\{a\} = \{ba\}$). Il a en plus un élément absorbant, $\emptyset$ : $L \cdot \emptyset = \emptyset \cdot L = \emptyset$, puisqu'on ne peut choisir aucun mot dans $\emptyset$.

Il est distributif sur l'union : $L_1 (L_2 \cup L_3) = L_1 L_2 \cup L_1 L_3$. Il ne l'est pas sur l'intersection. Avec $L_1 = \{a, ab\}$, $L_2 = \{b\}$, $L_3 = \{\varepsilon\}$ : $L_1(L_2 \cap L_3) = L_1 \cdot \emptyset = \emptyset$, alors que $L_1 L_2 \cap L_1 L_3 = \{ab, abb\} \cap \{a, ab\} = \{ab\}$.

Puissances et étoile

On note $L^n$ le produit de $n$ copies de $L$ : $L^0 = \{\varepsilon\}$, et $L^{n+1} = L^n \cdot L$. Un mot de $L^n$ est une concaténation de $n$ mots de $L$, choisis indépendamment.

C'est cette opération qui fait passer du fini à l'infini : dès que $L$ contient un mot non vide, $L^*$ est infini. Et c'est d'elle que vient la notation $\Sigma^*$ : en voyant l'alphabet comme le langage des mots d'une lettre, $\Sigma^*$ est l'ensemble des mots formés d'un nombre quelconque de lettres, c'est-à-dire de tous les mots.

Deux cas limites, qu'on retrouvera : $\emptyset^0 = \{\varepsilon\}$ par définition, et $\emptyset^n = \emptyset$ pour $n \geq 1$. Donc

L'étoile du langage vide n'est pas vide : elle contient le mot vide, qu'on obtient en ne choisissant aucun mot.

Quelques identités, qui se vérifient en revenant aux définitions :

Les opérations sur les mots, étendues aux langages

Toutes les notions de la première partie s'étendent aux langages, mot par mot :

• $\mathrm{Pref}(L)$ : les préfixes des mots de $L$ ;
• $\mathrm{Suff}(L)$ : les suffixes des mots de $L$ ;
• $\mathrm{Fact}(L)$ : les facteurs des mots de $L$ ;
• $L^t = \{u^t \mid u \in L\}$ : le transposé de $L$.

Par exemple, $\mathrm{Pref}(\{ab, ba\}) = \{\varepsilon, a, ab, b, ba\}$. Au chapitre 6, on se demandera si ces opérations préservent les langages rationnels.

Et maintenant ?

Un langage infini ne s'écrit pas en extension : on ne peut pas énumérer ses mots. Pour en parler, il faut une description finie. Les exemples de ce chapitre en ont donné plusieurs, en français (« les mots qui commencent par $a$ »), en notation mathématique ($\{a^n b^n \mid n \geq 0\}$), ou par des opérations ($\{a, ab\}^*$).

La dernière forme est la bonne piste : partir de langages très simples et les combiner par union, produit et étoile. C'est exactement ce que font les expressions rationnelles, au chapitre suivant.