Minimiser
Ce que ce chapitre apporte5 points
- 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 utile en soi : un contrôleur plus petit se relit plus vite. Mais c'est surtout la seule manière de comparer deux automates, parce que cette plus petite forme est unique. L'algorithme n'a qu'une difficulté, 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, et il porte un nom, le raffinement de partition, ou algorithme de Moore : 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
La règle s'applique maintenant au contrôleur de l'équipe A, tour après tour, jusqu'à ce qu'un tour ne coupe plus rien.
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 tous les deux mesures sur un ok et un défaut sur un defaut, donc classe I puis classe II de part et d'autre. arrêt et arrêt tenu répondent tous les deux arrêt tenu, donc classe IV pour les deux symboles. 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. Au tour 1, defaut n'avait isolé que deux défauts. Il a coupé de nouveau au tour 2, parce que deux défauts était entre-temps 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 | Mot qui prouve la coupure | Partition obtenue |
|---|---|---|---|
| 0 | aucun | le mot vide | {vide, après ok, défaut initial, défaut après ok, deux défauts} et {alerte} |
| 1 | defaut | defaut | {vide, après ok, défaut initial, défaut après ok}, {deux défauts}, {alerte} |
| 2 | defaut | defaut defaut | {vide, après ok}, {défaut initial, défaut après ok}, {deux défauts}, {alerte} |
Les deux mots de preuve se vérifient à la main. Le mot defaut est accepté depuis deux défauts et rejeté depuis les quatre autres états de la classe : c'est ce qui isole deux défauts au tour 1. Le mot defaut defaut est accepté depuis défaut initial et depuis défaut après ok, rejeté depuis vide et depuis après ok : c'est ce qui coupe la classe restante au tour 2.
Quatre classes, comme pour l'équipe A. Les quatre classes de A et celles de B se correspondent une à une, et reçoivent ici un nom commun, de 0 défaut à arrêt :
| Nom commun | Classe de A | Classe de B | Ce que la classe retient | ok mène à | defaut mène à |
|---|---|---|---|---|---|
0 défaut | {veille, mesures} | {vide, après ok} | aucun défaut consécutif, classe initiale | 0 défaut | 1 défaut |
1 défaut | {un défaut} | {défaut initial, défaut après ok} | un défaut consécutif | 0 défaut | 2 défauts |
2 défauts | {deux défauts} | {deux défauts} | deux défauts consécutifs | 0 défaut | arrêt |
arrêt | {arrêt, arrêt tenu} | {alerte} | arrêt déclenché, classe acceptante | arrêt | arrêt |
Les deux dernières colonnes valent pour A comme pour B, et c'est là que la comparaison se joue. Deux automates ne se comparent pas sur leurs noms ni sur leur nombre de cercles, mais case par case : même classe initiale, même classe acceptante, et même destination pour chaque symbole. Les deux contrôleurs 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 : le mot vidange, à lui seul, est accepté depuis chargée et rejeté depuis les trois autres états. Le tour 2 sépare encore avec charge, qui isole cette fois repos, et le mot qui le prouve a deux lettres, charge vidange, accepté depuis repos seul. 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, et le mot defaut le prouve, accepté depuis cumul 2 et rejeté depuis rien comme depuis cumul 1. Tour 2, séparateur defaut de nouveau : il isole cumul 1, et le mot de preuve a cette fois deux lettres, defaut defaut, accepté depuis cumul 1 et rejeté depuis rien. 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. Reste à 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, il ne relève plus de l'automate qui reconnaît le langage. Il relève 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.
Mettre en pratique
Le raffinement tour par tour, et le mot qui prouve que deux automates diffèrent.
Tous les exercices sur minimiser