Des automates aux expressions, le théorème de Kleene

La question

Au chapitre 4, on a montré $\mathrm{Rat} \subseteq \mathrm{Rec}$ : toute expression rationnelle se compile en automate. La question inverse se pose : tout langage reconnu par un automate est-il rationnel ? Autrement dit, pour un automate donné, existe-t-il une expression rationnelle équivalente ?

La réponse est oui, et comme au chapitre précédent on va la démontrer en donnant un algorithme.

Sur des exemples

Commençons par de petits automates, dont on lit l'expression à l'œil.

Un seul chemin réussi, étiqueté $a$ : l'expression est $a$.

Deux transitions en série : on les concatène, $ac$.

Une boucle sur l'état intermédiaire : on peut la faire un nombre quelconque de fois, $ab^*c$.

Deux chemins parallèles de 0 à 2 : on fait l'union, $ab^*c + d$.

Regardons ce qu'on a fait dans le dernier cas. Pour aller de 0 à 2, on peut passer par 1 (en lisant $ab^*c$) ou aller directement (en lisant $d$). Si on s'autorise à étiqueter les transitions par des expressions au lieu de lettres, on peut dessiner :

On vient de supprimer un état sans changer le langage. L'algorithme consiste à recommencer jusqu'à ce qu'il ne reste qu'une transition.

L'élimination d'états

Automates généralisés

Un automate ordinaire est un automate généralisé : une lettre est une expression, $\varepsilon$ aussi. On s'autorise une simplification : deux transitions de même origine et même destination, $p \xrightarrow{e} q$ et $p \xrightarrow{f} q$, se fusionnent en une seule, $p \xrightarrow{e + f} q$. Il y a donc au plus une transition par couple d'états, et on note $e_{pq}$ son étiquette.

Un initial et un final uniques

On veut arriver à un automate de la forme $I \xrightarrow{e} F$, dont l'étiquette $e$ sera l'expression cherchée. Mais un automate peut avoir plusieurs états initiaux ou finals. On commence donc par ajouter un nouvel état initial $I$ et un nouvel état final $F$, reliés par des transitions spontanées aux anciens :

$I$ n'a aucune transition entrante, $F$ aucune sortante. Le langage n'a pas changé. On retrouve l'invariant de Thompson.

Supprimer un état

On veut supprimer un état $J$, autre que $I$ et $F$, en préservant le langage. Pour cela, il faut que tous les chemins qui traversaient $J$ puissent passer autrement. Un chemin qui traverse $J$ y arrive depuis un prédécesseur $i$, y boucle un nombre quelconque de fois, et en repart vers un successeur $k$.

On remplace ce passage par une déviation directe de $i$ à $k$ :

La convention simplifie : s'il n'y avait pas de transition de $i$ à $k$, $\emptyset + f \equiv f$ ; s'il n'y avait pas de boucle sur $J$, $\emptyset^* \equiv \varepsilon$ et le facteur disparaît.

L'algorithme

Chaque étape supprime un état, et l'automate est fini : l'algorithme termine. Chaque suppression préserve le langage : le résultat est correct. On l'appelle aussi méthode d'élimination des états, ou BMC.

L'ordre dans lequel on supprime les états ne change pas le langage, mais il change l'expression obtenue, parfois beaucoup. Une bonne heuristique est de supprimer d'abord l'état qui crée le moins de déviations : celui dont le produit (nombre de prédécesseurs) × (nombre de successeurs), sans compter les boucles, est le plus petit.

Un exemple complet

Cherchons une expression pour cet automate sur $\{a, b, c\}$ :

Normalisation. On ajoute $I \xrightarrow{\varepsilon} 0$, $1 \xrightarrow{\varepsilon} F$ et $3 \xrightarrow{\varepsilon} F$.

Scores (prédécesseurs × successeurs, sans les boucles) :

On supprime 1. Prédécesseur 0 ; successeurs 3 et $F$. Deux déviations :

• $(0, 3)$ : $\emptyset + a\,\varepsilon\,b = ab$ ;
• $(0, F)$ : $\emptyset + a\,\varepsilon\,\varepsilon = a$.

Nouveaux scores : 0 a pour successeurs 2, 3 et $F$, score 3 ; 2 garde le score 2 ; 3 a pour prédécesseurs 0 et 2, successeurs 2 et $F$, score 4. On supprime 2. Prédécesseurs 0 et 3 ; successeur 3 ; boucle $a$.

• $(0, 3)$ : $ab + b\,a^*\,a = ab + ba^+$ ;
• $(3, 3)$ : $\emptyset + c\,a^*\,a = ca^+$. C'est le cas $i = k$ : une boucle sur 3.

On supprime 3 (score $1 \times 1$). Prédécesseur 0 ; successeur $F$ ; boucle $ca^+$.

• $(0, F)$ : $a + (ba^+ + ab)(ca^+)^*\varepsilon = (ba^+ + ab)(ca^+)^* + a$.

On supprime 0. Une seule déviation, $(I, F)$ : $\varepsilon \cdot ((ba^+ + ab)(ca^+)^* + a)$.

L'automate reconnaît

On peut le relire sur l'automate de départ : soit on s'arrête en 1 après $a$ ; soit on atteint 3 par $ab$ ou par $ba^+$, puis on y revient autant de fois qu'on veut par $ca^+$.

L'algorithme fonctionne toujours. Mais sur un automate plus gros, l'expression devient vite illisible, et sa taille peut croître exponentiellement avec le nombre d'états. Les expressions sont faites pour être écrites par des humains ; celles que produit une machine sont rarement belles.

Une autre méthode : les équations

On peut aussi calculer l'expression en résolvant un système d'équations. On associe à chaque état $q$ une inconnue $X_q$ : le langage des mots qui mènent de $q$ à un état final. Chaque état donne une équation, qui dit par où l'on peut sortir : « lire $a$ et aller en $q'$ », pour chaque transition $q \xrightarrow{a} q'$, et « s'arrêter », si $q$ est final.

Pour l'automate de l'avant-dernière lettre, de transitions $0 \xrightarrow{a,b} 0$, $0 \xrightarrow{a} 1$, $1 \xrightarrow{a,b} 2$, et d'état final 2 :

On substitue : $X_1 = a + b$, puis $X_0 = (a + b)X_0 + a(a + b)$. L'inconnue apparaît des deux côtés. C'est le rôle du lemme suivant.

Intuitivement : un mot de $X$ commence par un certain nombre de mots de $K$, puis se termine par un mot de $L$. La condition $\varepsilon \notin K$ assure l'unicité ; sans elle, $\Sigma^*$ serait aussi solution de $X = \{\varepsilon\}X$.

Ici, $K = a + b$ et $L = a(a + b)$ : $X_0 = (a + b)^*a(a + b)$, et c'est l'expression du langage, puisque 0 est l'état initial. Les deux méthodes donnent des expressions équivalentes, souvent différentes ; celle des équations se prête bien au calcul à la main sur de petits automates.

Le théorème de Kleene

On vient de démontrer $\mathrm{Rec} \subseteq \mathrm{Rat}$. Avec le chapitre 4 :

Ce sont deux ensembles identiques, décrits de deux façons de nature différente :

• les expressions rationnelles disent ce qu'est le langage : elles sont dénotationnelles ;
• les automates disent comment le reconnaître : ils sont opérationnels.

Leur point commun est d'avoir une mémoire finie. Et on sait passer de l'une à l'autre dans les deux sens, par des algorithmes.

En pratique, on n'a plus besoin de distinguer $\mathrm{Rat}$ et $\mathrm{Rec}$ : on parle de langages rationnels, et on choisit la description la plus commode pour la question posée. Pour montrer qu'un langage est rationnel, il suffit d'écrire une expression ou de dessiner un automate. Pour montrer une propriété des langages rationnels, on raisonne sur les expressions ou sur les automates, selon ce qui est le plus simple. C'est ce qu'on fait au chapitre suivant.