séquence 209_3

Attention, dans le point "2" de la définition précédente, le symbole ε représente deux notions différentes. Le premier est un symbole d'une expression rationnelle alors que le second symbolyse l'ensemble contenant uniquement le mot vide. Cependant, il y a isomorphisme entre ces deux notions.

Comme la réunion et la concaténation sont associatives, on omettra généralement les parenthèses inutiles. On écrira par exemple (u | v | w) plutôt que ((u |v) | w) ou (u | (v | w)) et de même pour la concaténation. Bien sûr, il est sous-entendu qu'aucun des symboles "|", "*", "ε", "(" et ")" n'appartient à l'alphabet A. Sinon, il faut soit les différencier en renomant les symboles, soit les entourer de guillemets.

Par exemple, le langage L={(({a}∪{b})*×{a})*×({b}×{c})*} peut être désigné par l'expression rationnelle((a|b)*a)*(bc)*.

En résumé, étant donné un alphabet A et C={ |, *, ε, (, )}, tel que A∩C=∅ :

Par exemple, 01 désigne le langage {01}, 0* désigne le langage {0}* et (0|1)*011 désigne le langage ne comportant que des chaînes se terminant par 011 sur l'alphabet {0,1}. Comme exemple plus complexe, on peut donner [A-Z,a-z][A-Z,a-z,0-9]* qui décrit la syntaxe des identificateurs en Pascal : des mots commençant par une lettre, majuscule ou minuscule ([A-Z,a-z]) et suivit d'une suite quelconque de caractères parmi les lettres et les chiffres ([A-Z,a-z,0-9]*).

Notons enfin que si wⁿ désigne bien un langage rationnel quand n est un entier fixé, par contre, ce n'est pas toujours vrai dans le cas général, quand n est une variable. En effet, par exemple, (ab)³ désigne ababab qui est une expression rationnelle, de même que [a,b]² qui désigne (a|b)(a|b). Par contre le langage désigné par aⁿbⁿ n'est pas rationnel : il s'agit des mots commençant par un certain nombre de a et suivis du même nombre de b, et ce langage ne peut pas être obtenu à partir des parties finies d'un alphabet A par simple application des opérations ×,∪ et *. Ceci illustre bien le fait que tout langage sur A n'est pas nécessairement rationnel. Il est possible de démontrer qu'un langage n'est pas rationnel (section sur le lemme de l'étoile).

En conséquence, si un langage peut être décrit par une expression rationnelle standard, c'est-à-dire utilisant uniquement les opérateur ×,∪ et *, alors ce langage est nécessairement rationnel. Cependant, l'expression standard, si elle existe nécessairement, peut s'avérer extrêmement complexe. Une autre façon de prouver qu'un langage est rationnel est, nous le verrons plus loin dans le cours, de construire un automate d'état fini reconnaissant ce langage. D'autres solutions consistent à décomposer le langage comme union, étoile ou concaténation de deux langages rationnels, à présenter une grammaire rationnelle ou d'essayer de décrire le complémentaire du langage. En effet, nous verrons plus loin que le complémentaire d'un langage rationnel est un langage rationnel (théorème). Enfin, nous verrons aussi que l'intersection de deux langages rationnels est un langage rationnel (théorème).

Les expressions rationnelles décrivent des langages, c'est-à-dire des ensembles de mots sur un alphabet A donné (souvent implicitement). De fait, il s'avère que deux expressions différentes peuvent décrire un même langage. Par exemple, a*a et aa* désignent toutes deux l'ensemble des chaînes de n a consécutifs pour n>0. On peut par ce biais définir une équivalence entre expressions rationnelles.

Soient, u, v et w des expressions rationnelles, on a entre autres les propriétés suivantes :

Par exemple, dans le mot "bbaab" du langage décrit par bb(a²)*b, le facteur "aa" est un facteur itérant.

Par exemple, "abab" n'est pas primitif alors que "ab" l'est sur l'alphabet {a,b}.

Exercices et tests :

Exercice 3.1. Ecrire les expressions rationnelles décrivant les langages suivants :

{ab}
{aⁿba^m, n ≥ 0, m ≥ 0}
{aⁿ, n ≥ 2}

Exercice 3.2. Décrire les langages définis par les expressions rationnelles suivantes (on donne d'abord l'alphabet puis l'expression) :

A₁={0,1,2,3,4,5,6,7,8,9,H}, ([1-9][0-9]^*(0|2|4|6|8)) | (0|2|4|6|8)
A₁, ([0-9]|10|11|12)H[0-5][0-9]
A₂={a,b, ..., z}, regarder(ai|as|a|ons|ez|ont)
A₃={a,b,c}, ((a|b|c)(a|b|c)(a|b|c))*
A₃, (a|b|c)*a(a|b|c)*a(a|b|c)
A₃, (b|c)*a(b|c)*a(b|c)*

Exercice 3.3. Donner l'alphabet (si nécessaire) et l'expression rationnelle permettant de décrire :

le langage dont les mots sont les nombres décimaux ;
Les mots sur {a,b} qui contiennent au moins un b et ne peuvent avoir deux b consécutifs (c'est à dire que bb ne peut être un facteur des mots du langage) ;
l'ensemble des mots sur {a,b,c} tels que toute paire de a est immédiatement suivie d'une paire de b.

Exercice 3.4. Pour chacune des expressions rationnelles suivantes, donner une expression rationnelle plus simple décrivant le même langage :

a⁺a*bc | aa?b?c
([a-z]*)*(c(ab)* | ca(b(ab)*))
a(ba)*b | (ab)⁺cd
a(ba)*b(bc|c) | ab*b?c

Exercice 3.5. Expression des chemins sous Unix

On veut représenter des noms complets de fichiers UNIX constitués d'un chemin absolu (c'est à dire partant de la racine) suivi du nom connu localement dans le répertoire. On considère que la longueur des chaînes à représenter n'est pas limitée et on impose les contraintes supplémentaires suivantes : toute sous-chaîne représentant un nom local de répertoire ou de fichier (c'est à dire comprise entre deux '/') ne doit ni être vide, ni se terminer par un '.', ni contenir deux points juxtaposés.

On se donne l'alphabet suivant : {A-Z,a-z,0-9,'.', '/','_'}

Ecrire une expression rationnelle (la plus simple possible) sur cet alphabet qui représente un nom complet de fichier UNIX tel qu'il est spécifié ci-dessus.

Exemples de chaînes à reconnaître :
- /home/Oscar/Annee.99/Algonum/exos.tar.gz
- /.forward
- /index.htm
- /home/Oscar/25_mai
- /A_B_C/Oscar/25_mai
Exemples de chaînes à ne pas reconnaître :
- /home/Oscar/Annee.99/Algonum/ (ne peut pas terminer par "/" car ce n'est pas un fichier)
- /. (ne peut pas terminer pas un ".")
- / ("/" seul n'est pas un fichier)
- exos.tar.gz (ce n'est pas un chemin absolu !)
- /forward. (termine pas un ".")

Exercice 3.6. Prouver que le langage suivant est rationnel : les mots sur {a,b} ne contenant pas la chaîne "aba".

Exercice 3.7. Expression rationnelles positives

Les expressions rationnelles positives sont définies, comme les expressions rationnelles, de manière inductive :

∅ et a, ∀ a ∈ A, sont des expressions rationnelles positives ;
si e et f sont des expressions rationnelles positives alors e|f, ef et e⁺ le sont aussi.

Le langage dénoté par une expression rationnelle positive est défini comme le langage dénoté par une expression rationnelle. On note PRat(A*) la famille des langages dénotés par une expression rationnelle positive.

Vérifier que ε n'appartient à aucun langage de PRat(A*).
Montrer que PRat(A*) ⊂ Rat(A*) .
Montrer que si L ∈ Rat(A*) alors L\ε ∈ PRat(A*).
Donner le principe de l'algorithme qui transforme une expression rationnelle en une expression rationnelle positive équivalente (à ε près).

3. Expressions rationnelles