À retenir
- Consiste à supprimer les états inaccessibles (qu'on ne peut pas atteindre).
- Consiste à supprimer les états non co-accessibles (qui ne mènent à aucune conclusion).
- Permet d'obtenir un automate plus compact et plus rapide à parcourir.
Émonder un automate consiste à faire le ménage dans son schéma de fonctionnement pour ne conserver que les parties utiles. Cela revient à supprimer les étapes que l'on ne peut jamais atteindre ou celles qui mènent à une impasse, un peu comme si l'on taillait les branches mortes d'un arbre pour ne garder que celles qui portent du fruit.
Étymologie
Issu du latin emundare, signifiant « nettoyer » ou « purifier ». À l'origine utilisé en agriculture pour la taille des arbres (enlever les branches inutiles), le terme a été adopté en informatique théorique pour décrire la simplification des structures logiques en retirant les éléments superflus.
Exemples d'usage
- Dans un correcteur orthographique, supprimer les chemins de lettres qui ne mèneront jamais à un mot correct.
- Dans un système de menus de borne automatique, retirer les options de navigation qui sont devenues inaccessibles suite à une mise à jour.
Cas d'usage
On utilise l'émondage principalement en théorie des automates, lors de la conception de compilateurs, dans le traitement automatique des langues ou pour optimiser des systèmes de vérification formelle de logiciels.
Bonnes pratiques
Il est recommandé d'émonder un automate après chaque opération de transformation (comme une union ou une intersection de deux automates), car ces étapes génèrent souvent de nombreux états inutiles qui ralentissent les calculs et consomment de la mémoire pour rien.
Synonymes
Conseil
Pour bien visualiser le concept, imaginez un labyrinthe : émonder revient à supprimer toutes les pièces fermées à clé (inaccessibles) et tous les couloirs qui finissent en cul-de-sac sans sortie.
Questions fréquentes
Quelle est la différence entre émonder et minimiser ?
L'émondage retire les parties mortes ou inaccessibles. La minimisation va plus loin en fusionnant les parties qui font exactement la même chose pour réduire l'automate à sa plus petite taille possible.
Pourquoi dit-on qu'un automate émondé est 'utile' ?
Parce que chaque état restant appartient au moins à un chemin complet allant du début à la fin de l'exécution.