Probleme – Minimiser, et décider l'équivalence

1. Le critère. Deux états $p$ et $q$ sont indistinguables si, pour tout mot $w$, lire $w$ depuis $p$ et depuis $q$ mène à des états tous deux acceptants ou tous deux non acceptants. Autrement dit, si les langages

$$L_p=\{w:{\delta }^{\ast }(p,w)\in F\}\text{et}{L}_q$$

— appelés résiduels — sont égaux. Un état ne sert qu'à retenir « ce qu'il reste à faire » ; deux états qui ont le même reste à faire sont un seul état.

2. L'algorithme de Moore. On ne peut pas tester « pour tout mot $w$ ». On raffine donc une partition, en séparant seulement quand on y est forcé :

• Partition initiale : deux classes, $F$ et son complémentaire. Ce sont les états distingués par le mot vide.
• Raffinement : deux états de la même classe sont séparés si, pour une lettre $x$, leurs images $\delta (p,x)$ et $\delta (q,x)$ tombent dans des classes différentes.
• On recommence tant que la partition change.

Terminaison. Variant : $|Q|-(\text{nombre de classes})$. Chaque tour qui change quelque chose augmente strictement le nombre de classes, qui est majoré par $|Q|$. Il y a donc au plus $|Q|-1$ tours.

Correction. Par récurrence : après $k$ tours, deux états sont dans la même classe si et seulement si aucun mot de longueur $\le k$ ne les distingue. La partition stabilisée est donc celle de l'indistinguabilité complète.

Complexité. Chaque tour parcourt tous les couples (état, lettre), soit $O(|Q|\cdot |\Sigma |)$, et il y a au plus $|Q|$ tours : $O(|Q{|}^2\cdot |\Sigma |)$. L'algorithme de Hopcroft descend à $O(|Q|\cdot |\Sigma |\cdot \log |Q|)$ ; on ne le demande pas.

3. L'exécution. On note la classe de chaque état, tour après tour.

La partition se stabilise en trois classes : $\{0\}$, $\{1\}$, $\{2,3\}$. Les états $2$ et $3$ sont confondus — tous deux acceptants, tous deux absorbants dans l'ensemble $\{2,3\}$. L'automate minimal a trois états, et son langage est celui des mots contenant le facteur aa : c'est l'automate de la figure du cours.

4. Décider l'équivalence. Deux méthodes, toutes deux correctes.

Par minimisation : l'automate minimal d'un langage régulier est unique à renommage près. On minimise les deux automates et l'on compare les tables.

Par produit et vacuité, plus simple à programmer : on complète les deux automates, on forme le produit reconnaissant $L(A)\setminus L(B)$, et l'on teste sa vacuité par un parcours en largeur ; puis on recommence en échangeant $A$ et $B$. C'est vide des deux côtés si et seulement si $L(A)=L(B)$ — et si ce n'est pas vide, le parcours rend le plus court mot témoin. Coût : $O(|Q_A|\cdot |Q_B|\cdot |\Sigma |)$.

Un chiffre qui donne la mesure de l'enjeu. L'automate de Glushkov de $(a|b{)}^{\ast }aa(a|b{)}^{\ast }$ a $7$ états. Déterminisé, il en a encore $7$. Minimisé, il en a 3 — et ces trois-là sont exactement ceux de l'automate écrit à la main dans le cours. Le test d'équivalence entre les deux le confirme : aucun mot ne les distingue, et les deux ont été comparés sur les $4095$ mots de longueur au plus $11$.

Ce que ce problème ajoute au chapitre. Il donne le sens exact de « le non-déterminisme n'ajoute pas d'expressivité » : non seulement l'automate déterminisé reconnaît le même langage, mais il existe un représentant canonique de ce langage, et l'on sait le calculer. C'est aussi ce qui rend l'équivalence décidable, ce qui n'a rien d'automatique — le chapitre chap:grammaires présente des objets pour lesquels la même question n'a pas de réponse algorithmique.