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 4
Des expressions aux automates
Compiler une expression rationnelle en automate déterministe, en trois étapes mécaniques. La construction de Thompson, l'élimination des transitions spontanées, la déterminisation par sous-ensembles.
La chaîne de compilation
On veut un programme qui, pour n'importe quelle expression rationnelle, construit un accepteur efficace, c'est-à-dire un DFA. On y arrive en trois étapes, chacune simple :
C'est ce que font, à quelques optimisations près, les générateurs d'analyseurs lexicaux comme lex ou flex : on leur donne des expressions, ils produisent un DFA sous forme de table, et un programme C qui l'exécute.
Première étape : la construction de Thompson
L'idée
Une expression rationnelle est une structure inductive : trois cas de base ($\emptyset$, $\varepsilon$, une lettre) et trois constructions ($+$, produit, étoile). On donne un automate pour chaque cas de base, et, pour chaque construction, une façon d'assembler les automates des sous-expressions. Six cas en tout, et on a un algorithme pour toutes les expressions.
Pour que les assemblages soient simples, tous les automates construits respectent un invariant :
On dessine un tel automate $A_e$, pour une expression $e$, comme une boîte dont on ne voit que l'entrée $i_e$ et la sortie $f_e$.
Les cas de base
Pour $\emptyset$ : deux états, et aucune transition. Aucun chemin ne va de $i$ à $f$, le langage est vide.
Pour $\varepsilon$ : une transition spontanée.
Pour une lettre $a$ : une transition étiquetée $a$.
Les constructions
Union. Pour $e + f$, un nouvel état initial choisit, sans rien lire, l'un des deux automates ; un nouvel état final les rejoint.
Produit. Pour $ef$, on enchaîne : la sortie de $A_e$ mène, sans rien lire, à l'entrée de $A_f$. L'initial de $A_e$ et le final de $A_f$ deviennent ceux du résultat.
Étoile. Pour $e^*$, on ajoute un nouvel initial et un nouveau final. Une transition spontanée de $f_e$ à $i_e$ permet de refaire un tour ; une transition de $i$ à $f$ permet de n'en faire aucun.
Dans les trois cas, le résultat respecte l'invariant. C'est lui qui garantit que les assemblages ne créent pas de chemins parasites. Par exemple, pour l'étoile, si $i_e$ avait des transitions entrantes, la boucle $f_e \to i_e$ permettrait de les emprunter en cours de tour, et de reconnaître des mots qui ne sont pas dans $L(e)^*$.
En effet, chaque cas de base crée deux états, l'union et l'étoile en ajoutent deux, le produit n'en ajoute aucun.
Un exemple
Pour $aa + ab$, on construit les automates des quatre lettres, on les enchaîne deux par deux pour $aa$ et $ab$, puis on réunit le tout.
Dix états : quatre lettres et un $+$ font cinq fois deux états.
Ce qu'on a prouvé
La construction marche pour toute expression, par induction sur sa structure : dans chacun des six cas, $L(A_e) = L(e)$, si c'est vrai pour les sous-expressions. On a donc démontré :
Et on a mieux qu'une preuve d'existence : un algorithme. Mais l'automate obtenu est un mauvais programme. Il a beaucoup de transitions spontanées, et la machine peut se trouver « à plusieurs endroits à la fois ». Il faut le transformer.
Deuxième étape : éliminer les transitions spontanées
Le principe
Une transition spontanée donne un choix à la machine : la franchir ou non, sans rien lire. On veut les supprimer, en compensant par des transitions ordinaires, de sorte que le langage ne change pas.
Reprenons l'automate de $a^*b^*c^*$ du chapitre précédent :
Depuis l'état 0, on peut lire un $b$ : en passant spontanément en 1, puis en lisant $b$. Pour que ce soit encore possible sans la transition spontanée, il faut une transition $0 \xrightarrow{b} 1$.
L'algorithme
Pour éliminer les transitions spontanées d'un $\varepsilon$-NFA :
- pour chaque transition propre (non spontanée) $p \xrightarrow{a} q$, et pour chaque état $r$ de $\mathrm{clo}^{-1}(p)$, ajouter la transition $r \xrightarrow{a} q$ ;
- rendre final tout état d'où un chemin spontané mène à un état final ;
- supprimer les transitions spontanées ;
- émonder, car certains états peuvent être devenus inaccessibles.
L'étape 1 dit : « si on pouvait atteindre $p$ sans rien lire puis lire $a$, on peut désormais lire $a$ directement ». L'étape 2 dit : « si on pouvait terminer en glissant vers un état final, on peut désormais terminer ici ».
Sur l'exemple
Les clôtures arrière sont $\mathrm{clo}^{-1}(0) = \{0\}$, $\mathrm{clo}^{-1}(1) = \{0, 1\}$, $\mathrm{clo}^{-1}(2) = \{0, 1, 2\}$.
- La transition $1 \xrightarrow{b} 1$ donne $0 \xrightarrow{b} 1$.
- La transition $2 \xrightarrow{c} 2$ donne $0 \xrightarrow{c} 2$ et $1 \xrightarrow{c} 2$.
- La transition $0 \xrightarrow{a} 0$ ne donne rien de nouveau.
Si on s'arrête là, en supprimant les transitions spontanées, on obtient :
C'est bien un NFA. Mais il n'est pas équivalent : il refuse $\varepsilon$, $a$ et $b$, que l'automate d'origine acceptait en glissant vers 2 à la fin. C'est l'étape 2 qui manque : 0 et 1 mènent spontanément à l'état final 2, ils deviennent finals.
Cet automate reconnaît bien $a^*b^*c^*$.
On a donc montré que tout $\varepsilon$-NFA a un NFA équivalent, de même nombre d'états. Mais le problème n'est pas réglé : le NFA obtenu a encore des choix.
Troisième étape : déterminiser
Le problème
Reprenons l'automate des mots dont l'avant-dernière lettre est $a$, c'est-à-dire $(a + b)^*a(a + b)$ :
C'est un NFA. Il n'est pas déterministe : de 0, en lisant $a$, on peut rester en 0 ou aller en 1. Pour cet exemple, on trouverait un DFA en réfléchissant. On veut une procédure mécanique, qui marche pour tous les NFA.
L'idée : suivre l'ensemble des états possibles
Au chapitre 3, pour exécuter un NFA, on a suivi l'ensemble des états où la machine peut se trouver. Après $aaba$, par exemple, elle peut être en 0 ou en 1. Suivre cet ensemble est déterministe : à un ensemble et une lettre correspond un seul ensemble suivant.
Il suffit donc de prendre ces ensembles d'états comme états d'un nouvel automate. Comme $Q$ est fini, il n'y a qu'un nombre fini de parties de $Q$ : le nouvel automate est fini.
L'algorithme
En pratique, on ne construit que les parties accessibles : on part de $I$, on calcule ses successeurs pour chaque lettre, puis les successeurs des nouvelles parties, et ainsi de suite jusqu'à ce qu'il n'en apparaisse plus. On range les calculs dans un tableau.
Sur l'exemple
| Partie | $a$ | $b$ | Finale ? |
|---|---|---|---|
| $\{0\}$ | $\{0, 1\}$ | $\{0\}$ | non |
| $\{0, 1\}$ | $\{0, 1, 2\}$ | $\{0, 2\}$ | non |
| $\{0, 1, 2\}$ | $\{0, 1, 2\}$ | $\{0, 2\}$ | oui |
| $\{0, 2\}$ | $\{0, 1\}$ | $\{0\}$ | oui |
Quatre parties seulement sont accessibles, sur les huit parties de $\{0, 1, 2\}$.
Vérifions : $aabaa$ mène de $\{0\}$ à $\{0, 1\}$, $\{0, 1, 2\}$, $\{0, 2\}$, $\{0, 1\}$, puis $\{0, 1, 2\}$, qui contient 2 : accepté, l'avant-dernière lettre est bien $a$. $aaba$ s'arrête en $\{0, 1\}$ : refusé.
On peut relire ce DFA : chaque état retient les deux dernières lettres lues. $\{0\}$ : pas de $a$ parmi elles ; $\{0, 1\}$ : elles finissent par $ba$ (ou le mot se réduit à $a$) ; $\{0, 1, 2\}$ : $aa$ ; $\{0, 2\}$ : $ab$. C'est exactement l'information nécessaire pour répondre.
Le résultat
La preuve est la construction : après la lecture d'un mot $u$, l'état de $D$ est exactement l'ensemble des états où $A$ peut se trouver après $u$. Donc $D$ accepte $u$ si et seulement si l'un de ces états est final, c'est-à-dire si $A$ accepte $u$.
Pour un $\varepsilon$-NFA, on peut soit éliminer d'abord les transitions spontanées, soit les intégrer à la construction : on remplace chaque partie par sa clôture avant, l'ensemble des états qu'on atteint depuis elle par des transitions spontanées. Les deux méthodes donnent des DFA équivalents.
Avec la construction de Thompson, on obtient :
La dernière inclusion est l'objet du chapitre 5. Une fois démontrée, toutes ces classes seront égales : les trois sortes d'automates reconnaissent exactement les mêmes langages.
Le coût
Un NFA à $n$ états a $2^n$ parties : le DFA peut avoir jusqu'à $2^n$ états. Ce n'est pas qu'une borne théorique. Pour le langage « la $k$-ième lettre avant la fin est un $a$ », soit $(a + b)^*a(a + b)^{k-1}$, le NFA a $k + 1$ états, et tout DFA équivalent en a au moins $2^k$ : il doit retenir les $k$ dernières lettres, et il y a $2^k$ possibilités.
En pratique, ces cas sont rares : pour les expressions qu'on écrit vraiment, le DFA reste le plus souvent de taille comparable au NFA. Et le coût est payé une fois, à la construction ; l'exécution, elle, reste linéaire en la longueur du mot.