Minimiser
Ce que ce chapitre apporte
- Dérouler le raffinement de partition, dit algorithme de Moore, en partant des deux classes initiales.
- Nommer, à chaque tour, le symbole séparateur qui coupe une classe en deux, et dire ce qu'il prouve.
- Justifier les deux conditions préalables, un automate déterministe et complet, et les obtenir quand elles manquent.
- Décider si deux automates reconnaissent le même langage, en les minimisant et en comparant les résultats.
- Exhiber un mot qui distingue deux automates lorsque la comparaison échoue.
Deux équipes reçoivent la même spécification et livrent deux contrôleurs. Les automates n'ont ni les mêmes états, ni les mêmes noms, ni le même nombre de cercles, et personne ne sait dire s'ils trient les colis de la même façon. Essayer des séquences au hasard ne prouve rien : elles peuvent coïncider sur cent journaux et diverger sur le cent unième. Ce chapitre donne la réponse exacte, et elle passe par une réduction. Réduire un automate déterministe à sa plus petite forme est un exercice utile en soi, puisqu'un contrôleur plus petit est un contrôleur plus rapide à relire ; mais c'est surtout la seule manière de comparer deux automates, parce que cette plus petite forme est unique. La difficulté de l'algorithme tient en une phrase, et elle est contre-intuitive : on ne regroupe jamais deux états parce qu'ils se ressemblent, on les sépare quand on trouve la preuve qu'ils diffèrent. Le point de départ est un automate déterministe et complet, tel que la construction des sous-ensembles le produit.
Deux contrôleurs pour un même tri
La spécification : un poste de tri lit le journal d'un colis, symbole par symbole, où ok est un contrôle réussi et defaut un contrôle raté. Le colis part au rebut dès que trois défauts consécutifs ont été relevés, et un ok remet le compteur à zéro.
L'équipe A a écrit son contrôleur en distinguant l'état de départ de l'état où des mesures ont déjà eu lieu, et en gardant un état de plus après le déclenchement de l'arrêt, pour journaliser.
okdefautdefautokdefautdefautdefaut
État actif : veille.
L'équipe B a préféré retenir ce qui précédait le défaut courant, ce qui lui donne deux états de défaut isolé au lieu d'un.
okdefautdefautokdefautdefautdefaut
État actif : vide.
Les deux automates ont six états, acceptent le mot proposé, et rejettent le second. Cela ne prouve rien du tout : deux contrôleurs différents peuvent coïncider sur tous les journaux essayés. La question reste entière, et elle se règle en réduisant chacun à sa forme minimale.
Séparer, et non regrouper
L'objectif est de fusionner les états qui font la même chose. La tentation est de les chercher directement, en comparant leurs flèches ou leurs noms. L'algorithme fait l'inverse : il suppose au départ que tout ce qui peut fusionner fusionne, puis cherche des preuves du contraire.
Deux états d'un automate déterministe sont équivalents lorsque, pour tout mot, la lecture de ce mot depuis l'un et depuis l'autre aboutit soit dans deux états acceptants, soit dans deux états non acceptants. Autrement dit, aucun mot ne permet de les distinguer. Deux états sont séparés dès qu'un mot les distingue, et ce mot est la preuve qu'ils ne peuvent pas fusionner.
Le départ de l'algorithme est la seule séparation connue sans calcul : un état acceptant et un état non acceptant sont distingués par le mot vide, puisque s'arrêter là donne déjà deux verdicts différents. D'où deux classes : les acceptants d'un côté, tous les autres de l'autre.
Ensuite, une seule règle, appliquée jusqu'à épuisement :
Si deux états d'une même classe sont envoyés par un même symbole dans deux classes différentes, ils ne sont pas équivalents et la classe se coupe. Ce symbole est le séparateur : il est la première lettre du mot qui distingue les deux états, la suite du mot étant celui qui distinguait déjà les deux classes d'arrivée.
Rien ne se regroupe jamais au cours de l'algorithme : les classes ne font que se couper. Quand plus aucun symbole ne coupe quoi que ce soit, ce qui reste ensemble est ensemble pour de bon, et chaque classe devient un état de l'automate minimal.
Le raffinement, tour par tour
Tour 0. Deux classes, sur le contrôleur de l'équipe A :
| Classe | États |
|---|---|
| I | veille, mesures, un défaut, deux défauts |
| II | arrêt, arrêt tenu |
Tour 1. Chaque symbole est essayé sur chaque classe. Le symbole ok d'abord : depuis veille, mesures, un défaut et deux défauts, il mène toujours dans mesures, donc dans la classe I. Les quatre états ont la même réponse, et ok ne sépare rien dans la classe I ; dans la classe II, arrêt et arrêt tenu mènent tous deux dans arrêt tenu, donc dans II. Aucune coupure.
Le symbole defaut ensuite :
| État de la classe I | defaut mène à | Classe d'arrivée |
|---|---|---|
veille | un défaut | I |
mesures | un défaut | I |
un défaut | deux défauts | I |
deux défauts | arrêt | II |
deux défauts est le seul à sortir de la classe I : le séparateur est defaut, et il isole deux défauts des trois autres. La preuve est lisible : le mot defaut mène deux défauts dans un état acceptant, et les trois autres dans un état non acceptant.
| Classe | États |
|---|---|
| I | veille, mesures, un défaut |
| II | deux défauts |
| III | arrêt, arrêt tenu |
Les deux figures suivantes sont ce même contrôleur, redémarré ailleurs : la première part de un défaut, la seconde de deux défauts, et toutes deux lisent le mot d'un seul symbole defaut.
defaut
État actif : un défaut.
defaut
État actif : deux défauts.
Le mot defaut est rejeté depuis un défaut et accepté depuis deux défauts. Un mot d'une seule lettre suffit donc à séparer deux états que leur dessin rendait presque identiques : même symbole entrant, même retour vers mesures sur un ok. C'est le sens exact de la règle, et c'est aussi pourquoi l'algorithme sépare au lieu de regrouper : une ressemblance ne se démontre pas en regardant, alors qu'une différence tient dans une lettre.
Tour 2. Le symbole ok ne sépare toujours rien, puisqu'il envoie tout le monde dans mesures. Le symbole defaut, lui, a maintenant trois classes pour destinations :
| État de la classe I | defaut mène à | Classe d'arrivée |
|---|---|---|
veille | un défaut | I |
mesures | un défaut | I |
un défaut | deux défauts | II |
Le séparateur est encore defaut, et il isole cette fois un défaut. Le mot qui le prouve a maintenant deux lettres, defaut defaut : depuis un défaut il mène à l'arrêt, depuis veille ou mesures il n'y mène pas.
| Classe | États | Ce que la classe retient |
|---|---|---|
| I | veille, mesures | aucun défaut consécutif en cours |
| II | un défaut | un défaut consécutif |
| III | deux défauts | deux défauts consécutifs |
| IV | arrêt, arrêt tenu | arrêt déclenché, acceptante |
Tour 3. Ni ok ni defaut ne coupent plus rien : veille et mesures répondent mesures puis un défaut, donc classe I puis classe II, tous les deux ; arrêt et arrêt tenu répondent arrêt tenu deux fois, donc classe IV deux fois. L'algorithme s'arrête, et le contrôleur de l'équipe A se réduit à quatre états.
L'arrêt de l'algorithme se constate, il ne se devine pas : il faut essayer tous les symboles sur toutes les classes et n'obtenir aucune coupure. Un tour où un seul symbole sépare relance le processus, car la nouvelle partition peut rendre séparateur un symbole qui ne l'était pas au tour précédent. C'est exactement ce qui vient de se produire : defaut n'avait rien séparé de plus au tour 1 que deux défauts, et il a coupé de nouveau au tour 2, parce que deux défauts était devenu une classe à lui seul.
Comparer les deux contrôleurs
Le contrôleur de l'équipe B se traite de la même façon, et les deux mêmes tours suffisent.
| Tour | Séparateur | Partition obtenue |
|---|---|---|
| 0 | aucun | {vide, après ok, défaut initial, défaut après ok, deux défauts} et {alerte} |
| 1 | defaut | {vide, après ok, défaut initial, défaut après ok}, {deux défauts}, {alerte} |
| 2 | defaut | {vide, après ok}, {défaut initial, défaut après ok}, {deux défauts}, {alerte} |
Quatre classes, comme pour l'équipe A. Et la comparaison se fait classe par classe :
| Classe de A | Classe de B | Rôle | Nom commun |
|---|---|---|---|
{veille, mesures} | {vide, après ok} | aucun défaut consécutif, classe initiale | 0 défaut |
{un défaut} | {défaut initial, défaut après ok} | un défaut consécutif | 1 défaut |
{deux défauts} | {deux défauts} | deux défauts consécutifs | 2 défauts |
{arrêt, arrêt tenu} | {alerte} | arrêt déclenché, classe acceptante | arrêt |
Les deux automates minimaux ont le même nombre d'états, la classe initiale correspond à la classe initiale, la classe acceptante à la classe acceptante, et chaque transition mène à la classe correspondante. Ils sont donc le même automate à un renommage près, et le voici.
okdefautdefautokdefautdefautdefaut
État actif : 0 défaut.
Pour un langage donné, l'automate déterministe complet minimal est unique à un renommage des états près. C'est ce qui rend la comparaison possible : deux automates reconnaissent le même langage si et seulement si leurs automates minimaux sont identiques, une fois les états inaccessibles supprimés. La comparaison de deux automates devient donc un calcul, et non plus une série d'essais.
Le gain pratique est double. Deux équipes peuvent vérifier qu'elles ont livré la même machine sans relire le code de l'autre, et un contrôleur peut être remplacé par sa version réduite en sachant qu'aucun journal, si long soit-il, ne sera trié différemment.
Déterministe et complet, sans quoi rien ne fonctionne
La règle de séparation parle de « la classe où ce symbole envoie l'état ». La formule suppose le déterminisme et la complétude, et l'algorithme les exige tous les deux.
Déterministe : sans cela, un symbole envoie un état dans plusieurs états à la fois, donc éventuellement dans plusieurs classes, et la signature d'un état n'est plus définie. Un automate non déterministe se déterminise d'abord, par la construction des sous-ensembles.
Complet : sans cela, une case manque, et « la classe d'arrivée » n'existe pas. Voici un contrôleur de cycle écrit sans l'état puits, avec un rebut explicite pour les colis défectueux.
chargecharge
État actif : repos.
La figure annonce « incomplet : une lecture peut se bloquer », et le mot charge charge le confirme : après le premier charge, l'état chargée n'a pas de transition pour un second. La minimisation ne peut pas commencer sur cet automate, non par formalisme, mais parce que la question « dans quelle classe charge envoie-t-il chargée ? » n'a pas de réponse.
La réparation a déjà servi deux fois : ajouter l'état puits, et y diriger toutes les cases manquantes.
chargecharge
État actif : repos.
L'automate est maintenant complet, donc minimisable, et le résultat mérite le détour. Le tour 1 sépare avec vidange, qui isole chargée, seul état d'où un vidange mène à l'acceptation. Le tour 2 sépare avec charge, qui isole repos, seul état restant d'où un charge mène à chargée. Il reste quatre classes, dont {rebut, puits} : le rebut écrit par l'ingénieur et le puits ajouté par la complétion sont le même état, puisque aucun mot ne mène de l'un ou de l'autre à l'acceptation.
Le raffinement classe tous les états, y compris ceux qu'aucun mot ne permet d'atteindre depuis l'état initial. Ceux-là ne changent pas le langage, mais ils peuvent survivre dans le résultat et fausser la comparaison de deux automates. Les supprimer est un travail préalable, à faire avant de commencer les tours : partir de l'état initial, suivre toutes les transitions, et jeter ce qui n'a jamais été atteint.
Exercices type
defautokdefautdefaut
État actif : rien.
Une équipe C livre le contrôleur ci-dessus. Le minimiser, puis dire s'il reconnaît le même langage que les contrôleurs A et B.
Le raffinement ne fusionne rien. Tour 0 : {rien, cumul 1, cumul 2} et {alerte totale}. Tour 1, séparateur defaut : il isole cumul 2, seul état d'où un défaut mène à l'alerte. Tour 2, séparateur defaut de nouveau : il isole cumul 1, seul état restant d'où un défaut mène à cumul 2. Quatre classes d'un état chacune : le contrôleur C est déjà minimal.
Il a donc quatre états, comme l'automate minimal commun de A et B, mais ce n'est pas le même : sur un ok, cumul 1 reste dans cumul 1, alors que 1 défaut revenait dans 0 défaut. Les deux automates minimaux diffèrent, donc les langages diffèrent.
C ne compte pas les défauts consécutifs, il compte les défauts du journal entier : un ok n'y remet rien à zéro.
Exhiber un mot aussi court que possible qui distingue le contrôleur C du contrôleur A, et vérifier le verdict de chacun.
Quatre symboles suffisent, par exemple defaut ok defaut defaut.
Sur C, les trois défauts sont comptés quel que soit l'ok intercalé : la lecture mène à alerte totale, le mot est accepté. Sur A, le ok renvoie dans mesures et remet le compteur à zéro : la lecture s'achève dans deux défauts, le mot est rejeté.
Aucun mot plus court ne convient. Sur un, deux ou trois symboles, seul defaut defaut defaut déclenche quoi que ce soit, et il le déclenche sur les deux contrôleurs à la fois : il faut au moins quatre symboles pour loger un ok entre trois défauts. D'autres mots de quatre symboles font l'affaire, comme defaut defaut ok defaut.
Ce mot est la réponse à donner à l'équipe C : il ne dit pas seulement que les deux contrôleurs diffèrent, il montre sur quel journal, ce qui permet de trancher laquelle des deux lectures de la spécification était la bonne.
Dans le contrôleur de l'équipe A, `arrêt` et `arrêt tenu` ont fusionné. Quel intérêt l'équipe avait-elle à les distinguer, et que perd-elle en les fusionnant ?
Les deux états ne diffèrent que par un usage hors langage : l'équipe voulait un état traversé une seule fois, celui où l'alarme se déclenche, distinct de l'état où l'arrêt se maintient. Vu du tri, la distinction ne change rien : depuis l'un comme depuis l'autre, tous les mots mènent à l'acceptation, donc aucun mot ne les sépare et le raffinement les réunit.
Ce que la fusion fait perdre n'est donc pas de la reconnaissance, c'est un point d'accroche pour une action. Si un effet doit se produire à l'entrée dans l'arrêt et pas ensuite, cet effet ne relève plus de l'automate qui reconnaît le langage, mais de ce que le programme fait au moment de la transition.
La leçon est générale : minimiser conserve exactement le langage, et rien d'autre. Un état gardé pour journaliser, pour tracer ou pour temporiser disparaîtra, et c'est le signe qu'il ne servait pas à reconnaître.
Vérification
1.Par quelles classes le raffinement de partition commence-t-il ?
2.Quand une classe se coupe-t-elle en deux ?
3.Que faut-il pour qu'un automate puisse être minimisé par cet algorithme ?
4.Un automate déterministe incomplet doit être minimisé. Que faire d'abord ?
5.Comment décider si deux automates reconnaissent le même langage ?
6.L'algorithme vient de faire un tour sans couper aucune classe. Que conclure ?
7.Deux états sont dans la même classe à la fin de l'algorithme. Qu'est-ce que cela signifie ?
La méthode
- Rendre l'automate déterministe par la construction des sous-ensembles s'il ne l'est pas.
- Le compléter en ajoutant l'état puits et en y dirigeant toutes les transitions manquantes.
- Supprimer les états inaccessibles depuis l'état initial, faute de quoi ils survivront dans le résultat.
- Partir de deux classes, les états acceptants et les autres.
- Essayer chaque symbole sur chaque classe : noter la classe d'arrivée de chaque état, et couper la classe dès que deux réponses diffèrent, en notant le séparateur.
- Recommencer tant qu'un tour coupe quelque chose, et s'arrêter au premier tour complet sans coupure.
- Construire l'automate minimal : une classe donne un état, la classe de l'état initial donne l'état initial, les classes contenant un état acceptant donnent les états acceptants.
- Comparer deux automates en confrontant leurs formes minimales, et, si elles diffèrent, en remontant le premier écart pour en tirer un mot qui les distingue.
Synthèse
- Deux états sont équivalents quand aucun mot ne mène de l'un à l'acceptation et de l'autre au rejet ; la minimisation fusionne les états équivalents.
- L'algorithme de raffinement de partition part de deux classes, les acceptants et les autres, et sépare au lieu de regrouper.
- Une classe se coupe dès qu'un symbole séparateur envoie deux de ses états dans des classes différentes ; ce symbole est la première lettre du mot qui distingue les deux états.
- L'algorithme s'arrête au premier tour qui ne coupe rien, et chaque classe restante devient un état de l'automate minimal.
- L'automate doit être déterministe et complet : le puits de la déterminisation est ce qui rend la minimisation possible, et il peut fusionner avec un état de rebut écrit à la main.
- L'automate minimal d'un langage est unique à un renommage près, ce qui permet de décider si deux automates reconnaissent le même langage : les minimiser, supprimer les états inaccessibles, et comparer.
- Quand les formes minimales diffèrent, un mot les distingue, et ce mot est le journal exact sur lequel les deux contrôleurs ne trient pas pareil.
Reste à savoir ce que ce modèle, même réduit à sa plus petite forme, ne pourra jamais reconnaître. Le chapitre sur ce qu'un automate ne sait pas faire le démontre, et en tire les contrôles qu'aucune expression régulière ne fera.