Émonder

Accessibles — parcours depuis $0$ : $\{0,1,2,3\}$. L'état $4$ n'est atteint par aucun mot.

Co-accessibles — parcours depuis $3$ dans l'automate transposé : $\{0,1,3,4\}$. L'état $2$ est un puits non acceptant : aucun mot ne le mène à $3$.

Émondé : on garde $\{0,1,3\}$, soit trois états sur cinq. Le langage est inchangé — il vaut $a^{+}b(a|b{)}^{\ast }$, les mots qui commencent par au moins un a puis rencontrent un b. L'accord avec l'automate d'origine a été vérifié sur les $4095$ mots de longueur au plus $11$.

Ce qu'on remarque, et qui est le point de l'exercice. L'automate émondé n'est plus complet : $\delta (0,b)$ a disparu avec l'état $2$. Émonder fait perdre la complétude. Or l'exercice sur le complémentaire a montré qu'échanger les acceptants d'un automate incomplet donne un résultat faux.

L'ordre des opérations est donc contraint : on émonde pour lire et pour comprendre un automate ; on complète pour calculer un complémentaire. Les deux transformations vont en sens inverse, et la seconde défait la première.

Les deux parcours coûtent $\Theta (|Q|\cdot |\Sigma |)$, soit une lecture de la table : émonder est gratuit devant tout le reste du chapitre.