Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter
Support de cours · chapitre 2
Expressions rationnelles
Décrire finiment des langages infinis. Les langages rationnels, les expressions qui les dénotent, leurs règles de calcul, et ce qui les sépare des regex des langages de programmation.
Quelles opérations garder ?
Le but
On cherche à décrire des langages, souvent infinis, par des formules finies et simples : simples à écrire, à lire, et, on le verra, à transformer en programme. L'idée du chapitre précédent était de partir de langages élémentaires et de les combiner. Reste à choisir lesquels, et avec quelles opérations.
Le tri
Passons en revue les candidats.
| Langage ou opération | Garder ? | Pourquoi |
|---|---|---|
| $\emptyset$ | oui | inutile en apparence, mais il faut bien pouvoir désigner le langage vide |
| $\{\varepsilon\}$ | oui | très utile : « rien », « facultatif » |
| $\{a\}$, pour $a \in \Sigma$ | oui | les briques de base |
| $L_1 \cup L_2$ | oui | le choix |
| $L_1 \cdot L_2$ | oui | la succession |
| $L^*$ | oui | la répétition, la seule source d'infini |
| $\Sigma^*$ | non | c'est $(\{a\} \cup \{b\})^*$ : on sait déjà l'obtenir |
| $L_1 \cap L_2$ | non | on n'en a pas besoin pour la définition (on verra qu'on n'y perd rien) |
| $\overline{L}$, $L_1 \setminus L_2$ | non | même remarque |
Sur $\emptyset$ : il ne sert presque à rien. $L \cup \emptyset = L$ (il est neutre pour l'union), $L \cdot \emptyset = \emptyset$ (il est absorbant pour le produit), $\emptyset^* = \{\varepsilon\}$. Mais sans lui, on ne pourrait pas nommer le langage vide, et certains algorithmes en produisent. On le garde.
Les six opérations retenues s'appellent les opérations rationnelles.
Les langages rationnels
« Le plus petit » veut dire : un langage est rationnel si et seulement s'il s'obtient à partir des langages de base par un nombre fini d'opérations rationnelles. C'est une définition inductive, et les preuves sur les langages rationnels se feront par induction : on traite les trois cas de base, puis les trois cas inductifs.
Tous les langages ne sont pas rationnels : on démontrera au chapitre 7 que $\{a^n b^n \mid n \geq 0\}$ ne l'est pas.
Les expressions rationnelles
Syntaxe
Écrire $\{a\} \cdot (\{a\} \cup \{b\})^*$ est pénible. On se donne une écriture plus légère, où chaque langage de base et chaque opération a son symbole.
Sémantique
Une expression dénote un langage. On note $L(e)$ le langage dénoté par $e$ :
| Expression | Langage dénoté |
|---|---|
| $\emptyset$ | $L(\emptyset) = \emptyset$ |
| $\varepsilon$ | $L(\varepsilon) = \{\varepsilon\}$ |
| $a$ | $L(a) = \{a\}$ |
| $e + f$ | $L(e + f) = L(e) \cup L(f)$ |
| $ef$ | $L(ef) = L(e) \cdot L(f)$ |
| $e^*$ | $L(e^*) = L(e)^*$ |
L'union s'écrit $+$ parce qu'elle se comporte comme une addition : elle est associative, commutative, de neutre $\emptyset$, et le produit se distribue dessus. L'analogie s'arrête là : $e + e = e$, ce qui n'a rien d'une addition.
Un langage est donc rationnel si et seulement s'il est dénoté par au moins une expression rationnelle.
Un détail d'orthographe, qui n'en est pas un en examen : on écrit expression rationnelle en français, rational ou regular expression en anglais.
Priorités
Pour alléger, on fixe des priorités, comme en arithmétique : l'étoile d'abord, puis le produit, puis l'union.
L'étoile ne porte que sur ce qui la précède immédiatement : $ab^*$ dénote $a$, $ab$, $abb$…, tandis que $(ab)^*$ dénote $\varepsilon$, $ab$, $abab$…
Équivalence
Deux expressions $e$ et $f$ sont équivalentes, et on écrit $e \equiv f$, si elles dénotent le même langage : $L(e) = L(f)$. Voici les équivalences d'usage courant ; toutes se prouvent en revenant aux langages.
| Équivalence | Nom |
|---|---|
| $e + (f + g) \equiv (e + f) + g$, $\quad e(fg) \equiv (ef)g$ | associativité |
| $e + f \equiv f + e$ | commutativité de l'union |
| $e + e \equiv e$ | idempotence de l'union |
| $e + \emptyset \equiv e$ | $\emptyset$ neutre pour l'union |
| $e\varepsilon \equiv \varepsilon e \equiv e$ | $\varepsilon$ neutre pour le produit |
| $e\emptyset \equiv \emptyset e \equiv \emptyset$ | $\emptyset$ absorbant pour le produit |
| $e(f + g) \equiv ef + eg$, $\quad (e + f)g \equiv eg + fg$ | distributivité |
| $\emptyset^* \equiv \varepsilon$, $\quad \varepsilon^* \equiv \varepsilon$ | |
| $(e^*)^* \equiv e^*$, $\quad e^* e^* \equiv e^*$ | |
| $e^* \equiv \varepsilon + ee^*$ | on s'arrête, ou on fait un tour de plus |
| $(e + f)^* \equiv (e^* f)^* e^*$ |
Le produit n'est pas commutatif : $ab \not\equiv ba$.
Tester l'équivalence de deux expressions par des calculs de ce genre demande de l'astuce, et on ne sait jamais si on a épuisé les possibilités. Au chapitre 6, on obtiendra un algorithme qui répond toujours.
Des exemples, et des définitions précises
Des nombres
Sur $\Sigma = \{0, 1\}$, les nombres binaires : au moins un chiffre.
Sur l'alphabet des dix chiffres, les nombres en base 10 :
C'est juste, mais on ne le lit plus. On y reviendra avec les abréviations.
Qu'est-ce qu'un nombre ?
L'expression précédente accepte $3$, $7$, $07$ et $007$. Est-ce ce qu'on veut ? Deux définitions sont légitimes :
- un nombre est une suite non vide de chiffres, et $007$ en est un ;
- un nombre n'a pas de zéro inutile en tête : $0$ est un nombre, $07$ n'en est pas.
La seconde s'écrit, en notant $c$ l'union des dix chiffres et $c'$ celle des neuf chiffres non nuls :
Aucune n'est la « bonne » : cela dépend de l'usage. En C, 7 et 07 sont deux constantes valides, mais 07 est écrit en octal ; 08 est refusé par le compilateur, puisque $8$ n'est pas un chiffre octal. La grammaire du C utilise encore une troisième définition. L'intérêt d'une expression rationnelle est de rendre la définition précise : une fois écrite, la question « $007$ est-il un nombre ? » a une réponse.
Abréviations
Les expressions réelles utilisent des notations supplémentaires. Ce ne sont pas de nouvelles opérations : chacune s'écrit avec les six de base, donc elle ne change pas l'ensemble des langages qu'on peut décrire.
| Notation | Signification | Exemple |
|---|---|---|
| $e^+$ | $ee^*$, au moins une fois | $(0 + 1)^+$ : les nombres binaires |
| $e?$ | $e + \varepsilon$, facultatif | $0?1$ : les mots $1$ et $01$ |
| $e^n$ | $e \cdots e$, $n$ fois | $(0+1)^8$ : un octet |
| $[abc]$ | $a + b + c$, une lettre parmi celles-ci | $[+-]$ |
| $[0-9]$ | $0 + 1 + \cdots + 9$, une lettre d'un intervalle | $[a-zA-Z]$ : une lettre |
Expressions rationnelles et regex
Les « regex » de grep, de Python ou de JavaScript descendent des expressions rationnelles, mais ce ne sont pas les mêmes objets.
- Elles cherchent un facteur.
grep 'ab'sélectionne les lignes qui contiennent $ab$. L'expression rationnelle $ab$ dénote le seul mot $ab$ ; la recherche degrepcorrespond à $\Sigma^* ab \Sigma^*$. Les ancres^et$servent à imposer le mot entier. - Elles ont des abréviations en plus :
.pour une lettre quelconque,\dpour un chiffre,{2,5}pour « de 2 à 5 fois ». Celles-là restent rationnelles. - Certaines extensions ne le sont pas. Les références arrière, comme
(a*)b\1, qui demande de répéter à droite ce qu'on a lu à gauche, décrivent $\{a^n b a^n \mid n \geq 0\}$. Ce langage n'est pas rationnel (même raisonnement que pour $a^nb^n$, au chapitre 7). C'est aussi pour cela que certaines regex s'exécutent en temps exponentiel, ce qui n'arrive jamais à une expression rationnelle compilée en automate (chapitre 4).