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 6
Propriétés de clôture
Quelles opérations préservent les langages rationnels ? Transposé, préfixes, facteurs, sous-mots, complémentaire, intersection, et le produit synchronisé, qui permet de tester l'inclusion et l'équivalence.
La question
On dit que $\mathrm{Rat}$ est clos par une opération si l'appliquer à des langages rationnels donne toujours un langage rationnel. Par définition, $\mathrm{Rat}$ est clos par union, produit et étoile. Qu'en est-il des autres opérations des chapitres 1 et 2 : transposé, préfixes, complémentaire, intersection ?
Grâce au théorème de Kleene, on a deux outils pour répondre, et on choisit à chaque fois le plus commode :
- raisonner sur les expressions, par induction sur leur structure ;
- raisonner sur les automates, en les transformant.
Dans les deux cas, la preuve est constructive : elle donne un algorithme qui calcule l'expression ou l'automate du résultat.
Dans tout le chapitre, $L$, $L_1$ et $L_2$ sont des langages rationnels.
Le transposé
$L^t$ contient les mots de $L$ écrits à l'envers. Est-il rationnel ? Oui.
Par les automates
On prend un automate de $L$, on inverse le sens de toutes les transitions, et on échange les états initiaux et finals. Un chemin réussi de l'automate d'origine, lu à l'envers, est un chemin réussi du nouvel automate, et son étiquette est transposée.
Le transposé d'un DFA n'est en général pas déterministe : plusieurs transitions de même lettre peuvent arriver dans un même état, et il y a autant d'initiaux que l'automate d'origine avait de finals.
Par les expressions
On définit $e^t$ par induction, en suivant les six cas. Il faut être attentif : la version naïve est fausse.
| $e$ | Proposition naïve | Juste |
|---|---|---|
| $\emptyset$ | $\emptyset$ | $\emptyset$ |
| $\varepsilon$ | $\varepsilon$ | $\varepsilon$ |
| $a$ | $a$ | $a$ |
| $e + f$ | $f + e$ | $e^t + f^t$ |
| $ef$ | $fe$ | $f^t e^t$ |
| $e^*$ | $e^*$ | $(e^t)^*$ |
La colonne naïve oublie de transposer les sous-expressions : c'est l'erreur type d'une définition par induction, où on applique la transformation au niveau courant sans la propager. Sur $e = (ab)c$, elle donne $c(ab)$, alors que le transposé de $abc$ est $cba$. La colonne juste donne $c^t (ab)^t = c\,(b^t a^t) = cba$.
L'ordre dans l'union n'a aucune importance ($e^t + f^t \equiv f^t + e^t$) ; dans le produit, il est essentiel.
Préfixes, suffixes, facteurs
Préfixes
$\mathrm{Pref}(L)$ est-il rationnel ? Oui. Un mot $u$ est un préfixe d'un mot de $L$ s'il existe une suite $w$ telle que $uw \in L$. Sur un automate : $u$ mène de l'initial à un état $q$ d'où l'on peut encore atteindre un état final, c'est-à-dire un état co-accessible. D'où la construction : rendre finals tous les états co-accessibles.
L'état 3 n'est pas co-accessible : si on le rendait final, on accepterait $b$, qui n'est préfixe d'aucun mot de $ab^*c$. On émonde d'abord, puis on rend tout final.
$\mathrm{Pref}(ab^*c) = \varepsilon + ab^* + ab^*c$.
Suffixes
$\mathrm{Suff}(L)$ est-il rationnel ? Oui, par la construction symétrique : on rend initiaux tous les états accessibles. On peut aussi réutiliser ce qu'on sait déjà :
Un suffixe de $u$, écrit à l'envers, est un préfixe de $u^t$.
Facteurs
$\mathrm{Fact}(L)$ est-il rationnel ? Oui : un facteur est un préfixe d'un suffixe,
Sur l'automate émondé, cela revient à rendre tous les états à la fois initiaux et finals.
Les sous-mots
Le langage des sous-mots des mots de $L$ est-il rationnel ? Oui.
Par les automates. Un sous-mot s'obtient en effaçant des lettres. On double donc chaque transition $p \xrightarrow{a} q$ par une transition spontanée $p \xrightarrow{\varepsilon} q$, qui permet de franchir la transition sans lire sa lettre.
(La boucle $1 \xrightarrow{\varepsilon} 1$ ne sert à rien, on ne la dessine pas.)
Par les expressions. On remplace chaque lettre $a$ par $a + \varepsilon$, et on ne touche à rien d'autre :
| $e$ | Sous-mots |
|---|---|
| $\emptyset$ | $\emptyset$ |
| $\varepsilon$ | $\varepsilon$ |
| $a$ | $a + \varepsilon$ |
| $e + f$ | $\mathrm{SM}(e) + \mathrm{SM}(f)$ |
| $ef$ | $\mathrm{SM}(e)\,\mathrm{SM}(f)$ |
| $e^*$ | $\mathrm{SM}(e)^*$ |
Ainsi $ab^*c$ devient $(a + \varepsilon)(b + \varepsilon)^*(c + \varepsilon) \equiv (a + \varepsilon)b^*(c + \varepsilon)$.
Union, complémentaire, intersection
Union
$L_1 \cup L_2$ est rationnel par définition : c'est une opération rationnelle. Pour les automates, on pose les deux côte à côte (plusieurs états initiaux sont permis), ou on applique la construction de Thompson.
Complémentaire
$\overline{L} = \Sigma^* \setminus L$ est-il rationnel ? Oui, mais la preuve demande de la précaution.
L'intuition est simple : un automate est une machine qui répond oui ou non avec une mémoire finie ; pour le complémentaire, il suffit de répondre l'inverse. D'où l'idée : échanger les états finals et non finals. Voyons si ça marche.
Premier essai, sur un NFA. Cet automate reconnaît $a^+$ :
Après l'échange :
Il accepte $a$, par le chemin qui reste en 0. Or $a \in L$ ! Dans un NFA, un mot est accepté s'il existe un chemin réussi ; son complémentaire demanderait qu'aucun chemin ne réussisse. Échanger les finals transforme « il existe un chemin qui finit dans $F$ » en « il existe un chemin qui finit hors de $F$ », ce qui n'est pas la négation. Il faut un automate déterministe, où chaque mot n'a qu'un chemin.
Deuxième essai, sur un DFA. Sur $\Sigma = \{a, b\}$, cet automate reconnaît $\{a\}$ :
Après l'échange :
Il n'accepte que $\varepsilon$. Et $b$, qui n'est pas dans $L$, n'est accepté par aucun des deux automates : la machine se bloque en le lisant, et un blocage vaut refus dans les deux cas. Il faut un automate complet, qui ne se bloque jamais.
Troisième essai, sur un DFA complet. On complète avec un puits, puis on échange :
Cette fois, chaque mot a exactement un chemin, qui finit dans un état final de l'un des deux automates et pas de l'autre.
Le coût est celui de la déterminisation : jusqu'à $2^n$ états pour un NFA à $n$ états.
Intersection
$L_1 \cap L_2$ est-il rationnel ? La question n'a rien d'évident : l'intersection ne fait pas partie des opérations rationnelles.
Première réponse, par les lois de De Morgan :
Le complémentaire et l'union préservent $\mathrm{Rat}$ : l'intersection aussi. Oui. Mais comme algorithme, c'est désastreux :
- le complémentaire de chaque automate demande de le déterminiser : jusqu'à $2^n$ états ;
- l'union, par Thompson, redonne un automate non déterministe ;
- le complémentaire final demande de déterminiser à nouveau : jusqu'à $2^{2^n}$ états.
Il faut une construction directe.
Le produit synchronisé
L'idée
Un mot est dans $L_1 \cap L_2$ s'il est accepté par l'automate $A_1$ et par l'automate $A_2$. On fait donc tourner les deux automates en même temps, sur le même mot : l'état de la machine combinée est un couple (état de $A_1$, état de $A_2$). Chaque lettre fait avancer les deux composantes.
Comme pour la déterminisation, on ne construit que les couples accessibles, en partant des couples initiaux.
Un exemple
$L_1$ : les mots ayant un nombre pair de $a$ (automate P / I du chapitre 3). $L_2$ : les mots qui finissent par $b$.
Le produit a pour état initial $(P, 0)$, et pour seul état final $(P, 1)$ : nombre pair de $a$, et dernière lettre $b$.
| Couple | $a$ | $b$ |
|---|---|---|
| $(P, 0)$ | $(I, 0)$ | $(P, 1)$ |
| $(P, 1)$ | $(I, 0)$ | $(P, 1)$ |
| $(I, 0)$ | $(P, 0)$ | $(I, 1)$ |
| $(I, 1)$ | $(P, 0)$ | $(I, 1)$ |
Ce qu'il coûte, ce qu'il permet
Le produit a au plus $n \times m$ états, contre $2^{2^n}$ pour De Morgan. Il marche aussi bien sur des NFA que sur des DFA, et le produit de deux DFA est un DFA.
En changeant seulement les états finals, le même produit donne d'autres opérations, à condition que les deux automates soient complets (sinon un blocage dans l'un arrête aussi l'autre) :
- union : les couples dont au moins une composante est finale, $(F_1 \times Q_2) \cup (Q_1 \times F_2)$ ;
- différence $L_1 \setminus L_2$ : les couples $(q_1, q_2)$ avec $q_1 \in F_1$ et $q_2 \notin F_2$, si $A_2$ est déterministe.
Décider
Le produit synchronisé répond à des questions qu'on ne savait pas trancher jusqu'ici.
Vacuité. $L(A) = \emptyset$ si et seulement si aucun état final n'est accessible. C'est un parcours de graphe.
Inclusion. $L_1 \subseteq L_2$ si et seulement si $L_1 \cap \overline{L_2} = \emptyset$. On complémente $A_2$ (déterminiser, compléter, échanger), on fait le produit avec $A_1$, et on teste la vacuité.
Équivalence. $L_1 = L_2$ si et seulement si $L_1 \subseteq L_2$ et $L_2 \subseteq L_1$.
Au chapitre 2, on se demandait comment savoir si deux expressions rationnelles sont équivalentes. On a maintenant un algorithme : compiler les deux expressions en automates, et tester l'équivalence. Il répond toujours, par oui ou par non. On dit que l'équivalence des expressions rationnelles est décidable. Le chapitre 7 donnera une autre méthode : comparer les automates minimaux.