Minimisation et limites

Ce qu'un automate retient

La question

Un même langage est reconnu par une infinité d'automates. Parmi les DFA complets qui le reconnaissent, en existe-t-il un plus petit ? Est-il unique ? Et sait-on le calculer ?

Pour répondre, il faut savoir ce qu'un automate doit retenir du début d'un mot pour pouvoir répondre à la fin.

Les résiduels

Le résiduel $u^{-1}L$ décrit exactement ce qu'il reste à lire pour être accepté, une fois qu'on a lu $u$. Deux débuts $u$ et $v$ qui ont le même résiduel sont interchangeables : la suite du mot ne permettra jamais de les distinguer.

Le lien avec les états

Dans un DFA complet, tous les mots qui mènent au même état $q$ ont le même résiduel : c'est le langage $L_q$ des mots qui mènent de $q$ à un état final. Donc un DFA complet a au moins autant d'états que $L$ a de résiduels.

Inversement, si $L$ n'a qu'un nombre fini de résiduels, on construit un DFA dont les états sont les résiduels :

• l'état initial est $\varepsilon^{-1}L = L$ ;
• la lettre $a$ mène de $R$ à $a^{-1}R$ ;
• les états finals sont les résiduels qui contiennent $\varepsilon$.

Après avoir lu $u$, cet automate est dans l'état $u^{-1}L$, et il accepte si $\varepsilon \in u^{-1}L$, c'est-à-dire si $u \in L$. Il reconnaît bien $L$, avec le nombre minimal d'états.

Le résiduel vide, s'il existe, correspond à l'état puits. Si l'on préfère les DFA non complets, on retire le puits, et le minimal a un état de moins.

Calculer l'automate minimal

L'idée

Partons d'un DFA complet dont tous les états sont accessibles. Deux états $p$ et $q$ sont équivalents s'ils ont le même langage : $L_p = L_q$. On peut alors les fusionner sans changer le langage reconnu. En fusionnant toutes les classes d'états équivalents, on obtient l'automate minimal.

Il reste à calculer ces classes. On ne peut pas comparer $L_p$ et $L_q$ directement, ce sont des ensembles infinis. On procède par raffinements successifs.

L'algorithme de Moore

On note $p \sim_k q$ si aucun mot de longueur au plus $k$ ne distingue $p$ et $q$ : pour tout $w$ avec $|w| \leq k$, $w$ mène de $p$ à un état final si et seulement s'il mène de $q$ à un état final.

Chaque rang découpe au moins une classe ou arrête l'algorithme ; il y a au plus $|Q|$ classes : on s'arrête en au plus $|Q|$ rangs.

Un exemple

Ce DFA complet reconnaît les mots qui contiennent au moins deux $a$ :

Rang 0 : finals $\{D, E\}$, non finals $\{A, B, C\}$.

Rang 1 : on regarde, pour chaque état, la classe de rang 0 de ses successeurs par $a$ et par $b$.

$B$ se sépare de $A$ et $C$ : trois classes, $\{A, C\}$, $\{B\}$, $\{D, E\}$.

Rang 2 : $A$ et $C$ vont tous deux en $B$ par $a$ et dans $\{A, C\}$ par $b$ ; $D$ et $E$ restent dans $\{D, E\}$. Rien ne se découpe : on s'arrête.

Trois états, qui retiennent « aucun $a$ », « un $a$ », « au moins deux $a$ ». C'est bien le minimum : les trois résiduels $L$, $a^{-1}L$ et $(aa)^{-1}L = \Sigma^*$ sont distincts.

Le coût est de l'ordre de $|Q|^2 \cdot |\Sigma|$. L'algorithme de Hopcroft, plus subtil, fait le même travail en $|Q| \log |Q| \cdot |\Sigma|$.

L'algorithme de Brzozowski

Il existe une autre méthode, surprenante. En notant $\mathrm{t}$ la transposition (chapitre 6) et $\mathrm{d}$ la déterminisation qui ne garde que les parties accessibles (chapitre 4) :

est l'automate minimal de $L(A)$, sans son éventuel puits, pour tout automate $A$, même non déterministe. On transpose, on déterminise, et on recommence. La méthode est facile à programmer si l'on a déjà ces deux opérations, mais chaque déterminisation peut coûter un nombre exponentiel d'états.

Une conséquence

L'automate minimal est unique. Pour savoir si deux expressions rationnelles sont équivalentes, on peut donc calculer l'automate minimal de chacune et vérifier que ce sont les mêmes, au nom des états près. C'est une seconde réponse à la question du chapitre 2, après le produit synchronisé du chapitre 6.

Ce qu'un automate ne peut pas retenir

Compter

Considérons $L = \{a^n b^n \mid n \geq 0\}$ : des $a$, puis autant de $b$. Pour le reconnaître, il faut se souvenir du nombre de $a$ lus, aussi grand soit-il. Un automate n'a qu'un nombre fini d'états : intuitivement, il ne peut pas.

Les résiduels le démontrent. Pour $k \neq k'$, le mot $b^k$ est dans $(a^k)^{-1}L$ et pas dans $(a^{k'})^{-1}L$ : les résiduels $(a^k)^{-1}L$ sont tous différents. $L$ a une infinité de résiduels : il n'est pas rationnel.

Les résiduels donnent une caractérisation exacte, mais il faut deviner la famille infinie de résiduels. Le lemme de l'étoile est un autre outil, souvent plus direct.

L'idée du lemme de l'étoile

Prenons un automate à 10 états et un mot accepté de 10 lettres. Le chemin qui l'accepte visite 11 états (celui du départ, puis un par lettre). Il n'y a que 10 états distincts : au moins un état $q$ est visité deux fois. Le chemin fait donc une boucle en $q$.

Découpons le mot en trois : $x$ mène de l'initial à $q$, $y$ fait la boucle de $q$ à $q$, $z$ mène de $q$ à un final.

La boucle $y$ n'est pas vide (on a lu au moins une lettre entre les deux passages en $q$). Mais $x$ ou $z$ peuvent l'être, si la boucle est sur l'état initial ou final. Et rien n'oblige à faire la boucle une seule fois : $xz$, $xyyz$, $xyyyz$… sont aussi acceptés.

L'énoncé

Preuve. Soit $A$ un DFA complet qui reconnaît $L$, et $k$ son nombre d'états. Soit $u \in L$ avec $|u| \geq k$. Les $k$ premières lettres de $u$ font visiter $k + 1$ états : l'un d'eux, $q$, est visité deux fois. On appelle $x$ le début de $u$ jusqu'au premier passage en $q$, $y$ la partie lue entre les deux passages, $z$ la fin. On a $y \neq \varepsilon$, $|xy| \leq k$, et l'on peut parcourir la boucle $y$ autant de fois qu'on veut, zéro compris. $\square$

L'entier $k$ est la taille d'un automate qui reconnaît $L$. Mais l'énoncé ne parle plus d'automate : il s'applique à tout langage rationnel, décrit comme on veut.

Ce n'est qu'une implication

Par exemple, $\{a^i b^j c^j \mid i \geq 1, j \geq 0\} \cup \{b^j c^k \mid j, k \geq 0\}$ vérifie la conclusion du lemme avec $k = 1$ (on pompe toujours la première lettre), et n'est pas rationnel (son intersection avec $ab^*c^*$ est $\{ab^jc^j\}$, qui ne l'est pas).

Le lemme ne sert donc jamais à montrer qu'un langage est rationnel. Il sert à montrer qu'un langage ne l'est pas, par contraposée : si l'on trouve, pour tout $k$, un mot long qui ne se pompe pas, le langage n'est pas rationnel.

Et les langages finis ? Ils sont rationnels, et vérifient le lemme sans difficulté : il suffit de prendre $k$ plus grand que le plus long mot. Aucun mot de $L$ n'a alors une longueur au moins $k$, et la condition est vide.

Montrer qu'un langage n'est pas rationnel

La preuve par le lemme de l'étoile a toujours la même forme, qu'on peut voir comme une partie contre un adversaire :

1. on suppose $L$ rationnel ; l'adversaire donne un $k$ ;
2. on choisit un mot $u \in L$ avec $|u| \geq k$, astucieusement ;
3. l'adversaire le découpe en $xyz$ avec $y \neq \varepsilon$ et $|xy| \leq k$ ; on doit traiter tous les découpages possibles ;
4. on trouve un $n$ tel que $xy^nz \notin L$ : contradiction.

Exemple : $a^n b^n$. Soit $k$ donné. On choisit $u = a^k b^k$. Comme $|xy| \leq k$, $x$ et $y$ ne contiennent que des $a$ : $y = a^j$ avec $j \geq 1$. Alors $xz = a^{k-j}b^k$ a moins de $a$ que de $b$ : il n'est pas dans $L$. Donc $L$ n'est pas rationnel.

Sans la condition $|xy| \leq k$, il faut examiner où se trouve $y$ : chez les $a$, chez les $b$, ou à cheval. Dans les deux premiers cas, répéter $y$ rompt l'équilibre ; dans le troisième, $xyyz$ contient un $b$ suivi d'un $a$. La condition $|xy| \leq k$ évite cette discussion : c'est pour cela qu'on choisit un mot dont le début est bien contrôlé.

Et les parenthèses ?

$a^n b^n$ paraît artificiel. Remplaçons $a$ par une parenthèse ouvrante et $b$ par une fermante : $\texttt{(}^n\,\texttt{)}^n$. Si le langage $P$ des mots bien parenthésés était rationnel, son intersection avec $\texttt{(}^*\texttt{)}^*$ le serait aussi (chapitre 6). Or cette intersection est $\{\texttt{(}^n\texttt{)}^n\}$, qui ne l'est pas. Donc $P$ n'est pas rationnel.

C'est un vrai problème pour l'informaticien : les expressions arithmétiques, les blocs { } du C, les balises HTML imbriquées ont tous cette structure. Les langages rationnels ne suffisent pas à décrire la syntaxe des langages de programmation. C'est pour cela qu'un compilateur utilise des expressions rationnelles pour découper le texte en mots (l'analyse lexicale), puis des grammaires, plus puissantes, pour en vérifier la structure (l'analyse syntaxique). Les langages qu'elles décrivent, les langages algébriques, sont reconnus par des automates munis d'une pile : une mémoire non bornée, mais qu'on ne consulte que par le dessus.