Déterminiser
Ce que ce chapitre apporte
- Énoncer le principe de la construction des sous-ensembles : un état du nouvel automate est un ensemble d'états de l'ancien.
- Dérouler la construction dans un tableau, ligne par ligne, chaque ligne naissant d'un ensemble déjà écrit.
- Traiter l'ensemble vide comme un état à part entière, l'état puits, et dire ce qu'il change à la lecture.
- Vérifier qu'un automate déterminisé est déterministe, complet, et qu'il accepte exactement les mêmes mots.
- Reconnaître les cas où le nombre d'états explose et ceux, bien plus fréquents, où il n'augmente pas.
Un automate non déterministe s'écrit en recopiant la spécification, mais il ne s'exécute pas facilement : à chaque symbole, il faut tenir à jour un ensemble d'états, le parcourir en entier, et recommencer. Un contrôleur embarqué, un analyseur de journaux ou un moteur d'expressions régulières ont besoin de l'inverse : un état courant, une case de tableau, et rien de plus. Ce chapitre construit cet automate déterministe à partir de l'automate non déterministe, sans rien deviner et sans rien inventer. La clé a déjà été montrée au chapitre sur le non-déterminisme : les états allumés en même temps forment un ensemble, et cet ensemble suffit à savoir quoi faire du symbole suivant. Il devient donc un état à lui tout seul.
Un état du nouvel automate est un ensemble d'états
L'automate qui cherche un motif noyé dans un flux d'événements revient ici tel quel : trois états, flux, chute vue et motif trouvé, sur les trois événements chute, surchauffe et mesure.
mesurechutemesuresurchauffe
État actif : flux.
Sur mesure chute mesure surchauffe, la figure allume successivement {flux}, {flux}, {flux, chute vue}, {flux, chute vue}, puis {flux, chute vue, motif trouvé}. Trois ensembles distincts seulement, sur les huit que trois états pourraient former.
L'observation décisive tient en une phrase : pour savoir quels états seront allumés après le prochain symbole, il suffit de connaître l'ensemble actuellement allumé. Ni le mot déjà lu, ni le chemin suivi, ni l'ordre dans lequel les états se sont allumés n'interviennent. Or c'est exactement la propriété que l'on demande à un état d'automate déterministe : contenir tout ce qu'il faut savoir pour traiter la suite.
Soit un automate non déterministe. La construction des sous-ensembles produit un automate déterministe reconnaissant le même langage, dont :
- les états sont des ensembles d'états de l'automate de départ ;
- l'état initial est la fermeture spontanée de l'état initial de départ ;
- la transition d'un ensemble
Epar un symbolesmène à l'ensemble de tous les états atteints depuis un état deEen lisants, fermeture spontanée comprise ; - les états acceptants sont les ensembles contenant au moins un état acceptant de départ.
La construction, ligne par ligne
La construction se tient dans un tableau à une colonne par symbole. Chaque ligne est un ensemble, donc un état du futur automate ; chaque case est l'ensemble atteint. Une ligne se traite une fois ; un ensemble qui apparaît dans une case sans avoir sa propre ligne en réclame une nouvelle.
Première ligne. Le départ est la fermeture spontanée de l'état initial. Cet automate n'a pas de transition spontanée, donc l'ensemble de départ est simplement {flux}. Pour chaque symbole, la question est : depuis flux, où mène ce symbole ?
chute: deux transitions partent deflux, l'une versflux, l'autre verschute vue. L'ensemble atteint est donc{flux, chute vue}. Il n'a pas encore de ligne : c'est une ligne à écrire.surchauffe: une seule transition, versflux. L'ensemble atteint est{flux}, déjà écrit.mesure: de même,{flux}.
Deuxième ligne. Elle traite {flux, chute vue}, l'ensemble né de la case précédente. Une case se calcule maintenant en réunissant deux départs, celui de flux et celui de chute vue.
chute: depuisflux,{flux, chute vue}; depuischute vue,{chute vue}. La réunion vaut{flux, chute vue}, la ligne courante elle-même.surchauffe: depuisflux,{flux}; depuischute vue,{chute vue, motif trouvé}, car cet état porte à la fois sa boucle et la sortie versmotif trouvé. La réunion vaut{flux, chute vue, motif trouvé}, un ensemble neuf, donc une troisième ligne à écrire.mesure:{flux}réuni à{chute vue}, soit{flux, chute vue}.
Troisième ligne. Elle traite {flux, chute vue, motif trouvé}. Les trois états bouclent sur eux-mêmes pour tout symbole, et motif trouvé n'a aucune autre sortie : chaque case redonne l'ensemble complet. Plus aucune case ne fait naître de ligne neuve, la construction s'arrête.
| Ensemble | chute | surchauffe | mesure |
|---|---|---|---|
{flux} | {flux, chute vue} | {flux} | {flux} |
{flux, chute vue} | {flux, chute vue} | {flux, chute vue, motif trouvé} | {flux, chute vue} |
{flux, chute vue, motif trouvé} acceptant | {flux, chute vue, motif trouvé} | {flux, chute vue, motif trouvé} | {flux, chute vue, motif trouvé} |
La troisième ligne est acceptante, et elle seule : c'est la seule à contenir motif trouvé. Le tableau est la table de transition d'un automate déterministe, à lire comme telle. Il suffit de le dessiner.
mesurechutemesuresurchauffe
État actif : {flux}.
L'en-tête annonce « Automate déterministe », la ligne de commentaire ne nomme plus qu'un état, et cet état porte en toutes lettres le nom de l'ensemble que l'automate non déterministe allumait au même instant. Les trois états ne sont pas des états nouveaux : ce sont les trois ensembles du tableau, et ils ont gardé leur nom pour que la correspondance reste lisible.
Le langage est conservé : un mot mène l'automate déterminisé dans l'ensemble exact des états que l'automate de départ aurait allumés, donc il est accepté par l'un si et seulement s'il l'est par l'autre. L'automate obtenu est déterministe par construction, puisque chaque case du tableau contient un ensemble et un seul, et complet, puisque chaque ligne possède une case par symbole.
L'ensemble vide est un état
Le premier exemple était complet, donc aucune case ne pouvait rester sans destination. Ce n'est pas le cas général. Voici l'automate du poste de contrôle, avec son séchage facultatif ouvert par une transition spontanée, soumis à un mot fautif : deux séchages de suite.
lavagesechagesechage
État actif : attente.
Au troisième symbole, la figure annonce que plus aucun état n'est actif : la lecture se bloque, et le dernier symbole n'est même pas lu. Un automate déterministe n'a pas le droit de se comporter ainsi, puisqu'une table de transition doit répondre pour chaque état et chaque symbole. La construction règle le problème toute seule, à condition de ne pas passer sous silence les cases où la réunion ne donne rien.
Départ. La fermeture spontanée de attente est {attente} : aucune transition spontanée n'en part.
lavagemène àlavée, dont la fermeture spontanée ajouteprête. L'ensemble atteint est{lavée, prête}, ligne neuve.sechage: aucune transition ne part deattenteavec ce symbole. L'ensemble atteint est vide, noté∅. C'est une ligne neuve comme les autres.controle: de même,∅.
Ligne {lavée, prête}. lavage ne mène nulle part depuis ces deux états, donc ∅. sechage mène lavée vers séchée, dont la fermeture ajoute prête : {séchée, prête}. controle mène prête vers validée : {validée}.
Ligne ∅. Il n'y a aucun état d'où partir, donc aucune destination : chaque symbole redonne ∅. La ligne est écrite en une fois, et elle ne fait naître aucune ligne neuve.
| Ensemble | lavage | sechage | controle |
|---|---|---|---|
{attente} | {lavée, prête} | ∅ | ∅ |
{lavée, prête} | ∅ | {séchée, prête} | {validée} |
∅ | ∅ | ∅ | ∅ |
{séchée, prête} | ∅ | ∅ | {validée} |
{validée} acceptant | ∅ | ∅ | ∅ |
L'état puits posé par la reconnaissance d'une séquence, celui qui absorbe une séquence déjà invalide, est ici l'ensemble vide ∅. Il ne contient aucun état acceptant, donc il n'est jamais acceptant ; toutes ses transitions reviennent sur lui, donc on n'en sort jamais. Y entrer signifie que tous les chemins ont échoué, et que rien de ce qui reste à lire ne peut y changer quoi que ce soit. Un automate déterministe sans état puits est un automate incomplet, c'est-à-dire un automate dont la table a des cases vides.
lavagesechagesechage
État actif : {attente}.
Le même mot fautif est cette fois lu en entier, et la lecture se termine dans ∅ : le verdict est le même, le mot est rejeté, mais il a été rejeté par un état plutôt que par un blocage. La différence n'est pas cosmétique. Un contrôleur qui se bloque n'a plus d'état courant à afficher, à journaliser ou à tester ; un contrôleur qui tombe dans le puits reste une machine en marche, capable de dire où elle en est. Et la minimisation exige justement un automate complet : le puits y sera un état comme un autre, et il pourra même fusionner avec d'autres.
∅ est un état, celui qui ne contient aucun état de l'automate de départ. Le mot vide est un mot, celui qui n'a aucun symbole, et sa lecture laisse l'automate sur son ensemble de départ. Un automate accepte le mot vide lorsque son ensemble initial contient déjà un état acceptant, ce qui n'a rien à voir avec l'existence du puits.
Quand la construction explose, et quand elle n'explose pas
Un automate à n états a 2ⁿ sous-ensembles. La construction ne peut donc pas produire plus de 2ⁿ états, et cette borne est parfois atteinte. Voici le cas type, écrit sur deux événements seulement, surchauffe et mesure : le journal est conforme si son avant-dernier événement est une surchauffe.
mesuresurchauffemesure
État actif : flux.
Trois états, et une seule idée : marqueur est le pari « cette surchauffe est l'avant-dernier événement ». La déterminisation donne quatre états, soit 2².
| Ensemble | surchauffe | mesure |
|---|---|---|
{flux} | {flux, marqueur} | {flux} |
{flux, marqueur} | {flux, marqueur, fin} | {flux, fin} |
{flux, marqueur, fin} acceptant | {flux, marqueur, fin} | {flux, fin} |
{flux, fin} acceptant | {flux, marqueur} | {flux} |
mesuresurchauffemesure
État actif : {flux}.
La raison de cette croissance se lit dans les ensembles : chacun encode ce qu'étaient les deux derniers événements. Il y a quatre possibilités, et aucune ne peut être confondue avec une autre, puisque la suite du journal les distingue. En remplaçant « avant-dernier » par « troisième événement avant la fin », l'automate non déterministe passe à quatre états, et le déterminisé à huit, exactement 2³. Pour le dixième événement avant la fin, l'automate non déterministe a onze états, et le déterminisé mille vingt-quatre.
L'explosion apparaît quand le non-déterminisme porte sur un pari qui ne se résout que bien plus tard, et que la résolution dépend de tout ce qui a été lu depuis : compter à partir de la fin en est l'exemple canonique. Elle n'apparaît pas quand le pari se résout sur place, ce qui est le cas de presque toutes les spécifications industrielles : un motif à chercher, une étape facultative, une réunion de deux séquences. Les deux automates déterminisés plus haut le montrent, avec trois états pour trois et cinq états pour cinq.
Deux raisons pratiques rassurent davantage encore. La construction ne fabrique que les ensembles atteignables, jamais les 2ⁿ du dénombrement : ce sont les ensembles que la figure du chapitre précédent allumait vraiment, et ils sont rarement nombreux. Et lorsque la croissance a bien lieu, elle est souvent réversible en partie : l'automate minimal réduit l'automate déterministe au plus petit qui reconnaisse le même langage.
Exercices type
surchauffemesuresurchauffe
État actif : flux.
Déterminiser l'automate ci-dessus, qui reconnaît les journaux se terminant par une `surchauffe`. Combien d'états le résultat compte-t-il, et l'ensemble vide apparaît-il ?
L'ensemble de départ est {flux}.
| Ensemble | surchauffe | chute | mesure |
|---|---|---|---|
{flux} | {flux, dernier vu} | {flux} | {flux} |
{flux, dernier vu} acceptant | {flux, dernier vu} | {flux} | {flux} |
surchauffemesuresurchauffe
État actif : {flux}.
Deux états, autant que l'automate de départ, et aucun ensemble vide : l'état flux ayant une transition pour chaque symbole, aucune réunion ne peut être vide. La déterminisation n'augmente donc pas toujours le nombre d'états, et ne crée un puits que là où l'automate de départ pouvait se bloquer.
Le résultat se lit comme un contrôleur évident : une surchauffe mène dans l'état acceptant, tout autre événement en sort. C'est bien la définition de « se termine par une surchauffe ».
L'automate des deux cycles de cuve allume trois états avant toute lecture, à cause de ses transitions spontanées. Quel est son ensemble de départ après déterminisation, et que devient la case `rincage` de la première ligne ?
L'ensemble de départ est la fermeture spontanée de l'état initial, donc {départ, purge 1, prod 1} : les deux branches sont ouvertes en même temps, exactement comme la figure l'affichait avant le premier clic.
La case purge de cette première ligne vaut {purge 2}, la case charge vaut {prod 2}, et les trois autres cases valent ∅, dont celle de rincage : aucun des trois états de départ n'a de transition pour ce symbole, puisque le rinçage ne peut pas ouvrir un cycle. La construction complète donne six états, dont le puits.
L'intérêt est visible dès la première ligne : le choix entre les deux cycles, qui était une transition spontanée, a disparu. Il est désormais tranché par le premier symbole lu, et l'automate déterministe n'a plus rien à choisir.
Un automate non déterministe possède 6 états. Un collègue affirme que le déterminiser donnera 64 états. Que répondre ?
2⁶ = 64 est une borne, pas une prévision. La construction ne fabrique que les ensembles réellement atteignables, ceux qui apparaissent dans une case du tableau, et il faut des automates très particuliers pour que les 64 sous-ensembles le soient.
La réponse honnête est donc : « au plus 64, et il faut dérouler le tableau pour savoir ». Sur les trois automates de ce chapitre, les résultats sont 3 états pour 3, 5 pour 5, et 4 pour 3. Le cas défavorable existe, il porte sur les propriétés qui comptent à partir de la fin du mot, et il reste reconnaissable à l'énoncé.
Reste que la borne n'est pas une clause de style : si l'automate de départ compte 40 états et que la spécification parle de la fin du mot, la table peut devenir inexploitable, et c'est alors la spécification qu'il faut rediscuter.
Vérification
1.Dans la construction des sous-ensembles, qu'est-ce qu'un état du nouvel automate ?
2.Quel est l'état initial de l'automate déterminisé ?
3.Un ensemble est acceptant dans l'automate déterminisé lorsque :
4.Que représente l'état ∅ dans l'automate déterminisé ?
5.Combien d'états au maximum peut compter la déterminisation d'un automate à 5 états ?
6.Pourquoi un automate obtenu par construction des sous-ensembles est-il toujours complet ?
7.Un mot bloque la lecture de l'automate non déterministe au troisième symbole. Que fait l'automate déterminisé sur ce mot ?
La méthode
- Écrire l'ensemble de départ : la fermeture spontanée de l'état initial, et non l'état initial seul.
- Ouvrir un tableau avec une colonne par symbole de l'alphabet, et tenir à part la liste des ensembles restant à traiter.
- Traiter une ligne : pour chaque symbole, réunir les destinations depuis tous les états de l'ensemble, puis appliquer la fermeture spontanée au résultat.
- Noter
∅quand la réunion est vide, et lui consacrer une ligne où chaque case vaut∅. - Ajouter à la liste tout ensemble apparu dans une case et qui n'a pas encore sa ligne, puis recommencer jusqu'à ce que la liste soit vide.
- Marquer acceptants les ensembles contenant au moins un état acceptant de l'automate de départ.
- Vérifier sur deux ou trois mots, dont un mot rejeté, que les deux automates rendent le même verdict.
Synthèse
- La construction des sous-ensembles transforme un automate non déterministe en automate déterministe reconnaissant le même langage.
- Un état du nouvel automate est un ensemble d'états de l'ancien : exactement l'ensemble que la figure allume à cet instant de la lecture.
- La construction se déroule dans un tableau, une ligne par ensemble, une colonne par symbole ; chaque case fait naître une ligne si son ensemble est neuf, et la construction s'arrête quand plus aucune ligne n'apparaît.
- L'ensemble vide est un état à part entière, l'état puits : il n'est jamais acceptant, on n'en sort jamais, et c'est lui qui rend l'automate complet là où l'automate de départ se bloquait.
- Un ensemble est acceptant dès qu'il contient un état acceptant de l'automate de départ.
- La borne
2ⁿest atteinte pour les propriétés qui se comptent à partir de la fin du mot ; dans les cas usuels, le nombre d'états ne bouge presque pas, parce que seuls les ensembles atteignables sont construits.
L'automate obtenu s'exécute, il n'est pas pour autant le plus petit. Le chapitre sur la minimisation le réduit à sa forme unique, et c'est cette unicité qui permet ensuite de décider si deux automates reconnaissent le même langage.