Le non-déterminisme : plusieurs états à la fois
Ce que ce chapitre apporte
- Reconnaître un automate non déterministe à ses deux signes : plusieurs transitions portant le même symbole depuis un même état, et les transitions spontanées.
- Lire une exécution où plusieurs états sont actifs en même temps, et dire ce que chaque état allumé représente.
- Appliquer la règle d'acceptation : un mot est accepté dès qu'un chemin mène à un état acceptant, même si tous les autres échouent.
- Suivre une transition spontanée ε, c'est-à-dire un état qui s'allume sans qu'aucun symbole ait été consommé.
- Écrire l'automate non déterministe qui cherche un motif noyé dans un flux d'événements.
Jusqu'ici, un automate se trouvait dans un état, et un seul : lire un symbole revenait à déplacer un jeton d'un cercle vers un autre. La règle est confortable, mais elle oblige à décider d'avance, pour chaque état et pour chaque symbole, ce que la machine doit faire. Or une spécification d'ingénieur se formule rarement ainsi. « Le journal contient une chute de pression suivie plus tard d'une surchauffe » ne dit rien des événements intermédiaires : c'est un motif, pas une procédure. Ce chapitre lève la contrainte, autorise plusieurs transitions pour un même symbole, autorise même des transitions qui ne lisent rien, et montre ce que devient l'exécution : non plus un jeton qui se déplace, mais un ensemble d'états allumés en même temps. La contrainte qu'il lève est le déterminisme exigé pour reconnaître une séquence.
Un seul état allumé : le cas déterministe
Une supervision de ligne de production reçoit un flux d'événements. Trois suffisent ici : chute pour une chute de pression, surchauffe pour un dépassement de température, et mesure pour un relevé de routine, celui qui remplit le journal sans jamais rien signaler. L'automate ci-dessous surveille une seule chose, le dernier événement reçu.
mesuresurchauffechute
État actif : flux.
La figure annonce « Automate déterministe », et la ligne de commentaire dit à chaque pas « État actif : flux » ou « État actif : surchauffe vue ». Un état, toujours un seul. C'est le sens du mot déterministe : l'état de départ et le symbole lu déterminent l'état d'arrivée, sans ambiguïté et sans rien à choisir.
Deux transitions pour un même symbole
Le langage à reconnaître change. Il ne s'agit plus du dernier événement, mais d'un motif : une chute de pression, puis, plus tard dans le journal, une surchauffe. Entre les deux, n'importe quoi. Écrire cela de façon déterministe demande de réfléchir ; l'écrire de façon non déterministe demande seulement de recopier la phrase.
L'automate suivant, réduit à deux événements pour commencer, contient deux transitions étiquetées chute au départ de l'état flux : l'une revient sur flux, l'autre part vers chute vue.
chutechutesurchauffe
État actif : flux.
La figure annonce maintenant « Automate non déterministe », et signale de surcroît qu'il est incomplet : certains états n'ont pas de transition pour tous les symboles, si bien qu'une lecture peut se bloquer. Les deux observations vont ensemble, et la déterminisation les traitera ensemble.
Au premier chute, la ligne de commentaire affiche « 2 états actifs en même temps : flux, chute vue. L'automate suit tous les chemins à la fois. » C'est la phrase qui donne son sens au chapitre. La machine ne choisit pas entre rester en flux et partir vers chute vue : elle fait les deux.
Un automate est non déterministe lorsqu'un état au moins possède, pour un même symbole, plusieurs transitions sortantes, ou lorsqu'il comporte des transitions spontanées. Son exécution ne manipule plus un état courant mais un ensemble d'états actifs : après chaque symbole lu, le nouvel ensemble réunit toutes les destinations atteintes depuis un état actif quelconque.
Ce qu'un état allumé signifie
Un état allumé n'est pas une machine qui se serait dédoublée, c'est une hypothèse encore vivante. Sur l'automate précédent, après le premier chute :
| État allumé | Hypothèse qu'il représente |
|---|---|
flux | la chute qui vient d'être lue ne fait pas partie du motif, le vrai motif commencera plus tard |
chute vue | la chute qui vient d'être lue est celle du motif, il reste à voir la surchauffe |
Rien ne permet de trancher au moment où le symbole est lu : la suite du journal le dira. Un automate déterministe est obligé de trancher tout de suite, donc d'encoder dans ses états de quoi le faire. Un automate non déterministe s'en dispense : il garde les deux hypothèses et laisse la lecture les départager.
Sur le mot chute chute surchauffe, le deuxième chute fait un travail intéressant. Depuis flux, il redonne flux et chute vue ; depuis chute vue, il ne mène nulle part, car cet état n'a pas de transition pour chute. L'hypothèse ouverte par la première chute meurt donc là, sans bruit, pendant que l'ensemble reste peuplé grâce à l'autre chemin. La figure affiche encore deux états actifs, et l'ensemble porte les mêmes noms, mais il ne dit plus la même chose : le chute vue allumé est désormais celui qu'ouvre la seconde chute.
Une lecture répandue veut que l'automate non déterministe « choisisse le bon chemin ». Elle est commode et fausse, et elle rend le reste du cours incompréhensible. La machine n'anticipe rien : elle explore tous les chemins en parallèle, et c'est la raison pour laquelle la figure allume plusieurs cercles à la fois, au lieu d'en désigner un seul par une clairvoyance qu'aucune machine ne possède.
Chercher un motif noyé dans un flux
Le journal réel ne contient pas que des chutes et des surchauffes. Il faut donc que les relevés de routine traversent l'automate sans rien perturber, où qu'ils tombent : avant la chute, entre la chute et la surchauffe, après la surchauffe. La recette tient en trois lignes, et chacune se lit comme un morceau de la spécification.
- Tant que le motif n'a pas commencé, tout événement laisse l'automate en
flux, et unechuteouvre en plus l'hypothèsechute vue. - En
chute vue, tout événement laisse l'automate enchute vue, et unesurchauffeouvre en plus la sortie versmotif trouvé. - Une fois en
motif trouvé, plus rien ne peut défaire ce qui a été vu.
mesurechutemesuresurchauffe
État actif : flux.
Cette fois l'automate est complet, la figure ne signale plus de blocage possible, et le déroulé sur mesure chute mesure surchauffe se lit ainsi :
| Symbole lu | États actifs après lecture | Ce qui vient de se passer |
|---|---|---|
| aucun | flux | position de départ |
mesure | flux | un relevé de routine, aucune hypothèse ouverte |
chute | flux, chute vue | l'hypothèse « le motif commence ici » s'ouvre, l'autre reste |
mesure | flux, chute vue | les deux hypothèses survivent à un événement neutre |
surchauffe | flux, chute vue, motif trouvé | le motif est complet sur un des chemins |
Trois états allumés à la fin, dont motif trouvé, qui est acceptant : le mot est accepté. Les deux autres ne gênent pas, et ne sont pas des erreurs : flux dit qu'un autre motif pourrait encore commencer, chute vue dit qu'une chute vue plus tôt attend toujours sa surchauffe. Ces hypothèses restent ouvertes parce que le journal, lui, n'est pas terminé.
Un mot est accepté par un automate non déterministe si l'ensemble des états actifs après lecture complète du mot contient au moins un état acceptant. Un seul chemin réussi suffit, quel que soit le nombre de chemins qui ont échoué. Le mot est rejeté quand tous les chemins échouent, c'est-à-dire quand aucun état acceptant n'est allumé à la fin, ou quand l'ensemble des états actifs s'est vidé en cours de route.
Le même automate, sur un journal où les deux événements arrivent dans le mauvais ordre :
surchauffemesurechutemesure
État actif : flux.
Deux états actifs à la fin, flux et chute vue, et le mot est pourtant rejeté : aucun des deux n'est acceptant. Le nombre d'états allumés ne dit rien du verdict ; seule compte la présence d'un acceptant parmi eux. En ajoutant surchauffe au bout du mot, l'hypothèse ouverte par la chute trouve enfin de quoi aboutir, et le verdict bascule.
Les transitions spontanées
Le second visage du non-déterminisme est une transition qui ne lit rien. Elle se note ε, se lit « epsilon », et signifie : l'automate peut passer d'un état à l'autre gratuitement, sans consommer de symbole. L'assemblage des expressions régulières en posait déjà à chaque brique ; il reste à regarder de près ce qu'elles font pendant une lecture.
Un poste de contrôle enchaîne trois opérations sur une pièce, un lavage, un sechage facultatif, puis un controle. Sans transition spontanée, il faudrait dupliquer la fin de l'automate pour tenir compte du séchage sauté. Avec une transition spontanée, l'étape se contourne d'un trait.
lavagecontrole
État actif : attente.
Après la lecture de lavage, la figure affiche deux états actifs, lavée et prête. Or un seul symbole a été lu, et une seule transition porte ce symbole. L'état prête s'est allumé tout seul, par la transition spontanée qui part de lavée : c'est exactement ce que veut dire « sans consommer de symbole ». Les deux états allumés disent les deux lectures possibles du cycle à cet instant : soit la pièce va passer au séchage, soit le séchage est sauté et la pièce est déjà prête pour le contrôle.
Le mot lavage controle est donc accepté, et lavage sechage controle aussi : après sechage, les états actifs sont séchée et prête, là encore parce que la transition spontanée issue de séchée s'ajoute gratuitement.
La fermeture spontanée d'un ensemble d'états est l'ensemble obtenu en y ajoutant tous les états atteignables par des transitions ε, puis en recommençant tant que de nouveaux états apparaissent. Elle s'applique à la position de départ, avant toute lecture, et après chaque symbole lu. Un état atteint par une transition spontanée est actif au même titre que les autres : rien ne le distingue une fois allumé.
La fermeture s'applique aussi avant le premier symbole, ce qui produit une figure surprenante : des états allumés alors que rien n'a été lu. Le cas se rencontre dès qu'un automate doit reconnaître l'une ou l'autre de deux séquences. Une cuve accepte deux cycles réglementaires, un nettoyage, purge puis rincage, et une production, charge, chauffe, vidange.
chargechauffevidange
3 états actifs en même temps : départ, purge 1, prod 1. L'automate suit tous les chemins à la fois.
Trois états sont actifs au départ : départ, purge 1 et prod 1. L'automate est entré dans les deux branches à la fois, sans rien lire, et le premier symbole tranchera. Dès charge, il ne reste qu'un état actif, prod 2 : la branche du nettoyage vient de mourir, faute de transition. La construction se généralise, et c'est elle qui sert à assembler des automates : deux automates reliés à un nouvel état initial par deux transitions spontanées reconnaissent la réunion de leurs deux langages.
ε n'est pas un événement que le journal contiendrait et qui s'écrirait avec zéro caractère. Ce n'est pas non plus un joker qui accepterait n'importe quel symbole. C'est un déplacement offert : l'automate a le droit de l'emprunter à tout instant, y compris plusieurs fois de suite, sans que la lecture du mot avance d'un pas. Un mot lu en entier reste lu en entier, quel que soit le nombre de transitions spontanées empruntées au passage.
Pourquoi ne pas écrire directement l'automate déterministe
L'objection est légitime : puisqu'un automate déterministe reconnaît le motif, autant l'écrire tout de suite. Le voici, avec trois états qui portent chacun une connaissance sûre, et non plus une hypothèse.
mesurechutemesuresurchauffe
État actif : avant.
Cet automate fonctionne, un seul état s'allume à chaque pas, et il est plus économique à faire tourner. Mais il a fallu le trouver. Chaque case de sa table de transition a demandé une décision : que faire d'une chute alors qu'une chute a déjà été vue, que faire d'une surchauffe avant toute chute, où renvoyer les relevés de routine dans chacun des trois états. Neuf décisions pour trois états et trois symboles, chacune prise à la main, chacune susceptible d'être fausse sans que rien ne le signale.
L'automate non déterministe, lui, s'est écrit par simple transcription de la phrase de spécification. Et l'écart se creuse avec la difficulté de l'énoncé : pour « une chute suivie d'une surchauffe dans les trois événements qui suivent », la version non déterministe ajoute deux états et rien d'autre, alors que la version déterministe doit mémoriser ce qui vient de se passer et se met à compter des cas.
L'automate non déterministe est la forme d'écriture : elle suit la spécification, mot à mot, sans réfléchir. L'automate déterministe est la forme d'exécution : un seul état à retenir, une seule transition à chercher par symbole, donc un contrôleur qui tient dans une table. Le chapitre sur la construction des sous-ensembles montre le passage mécanique de la première à la seconde, et il n'invente rien : chaque état du nouvel automate est exactement l'un des ensembles d'états que ces figures viennent d'allumer.
Exercices type
chutemesuresurchauffe
État actif : flux.
L'automate ci-dessus ressemble à celui du motif, mais l'état `chute vue` n'a plus de boucle. Quel langage reconnaît-il, et qu'affiche-t-il sur « chute mesure surchauffe », puis sur « mesure chute surchauffe » ?
Sans boucle sur chute vue, l'hypothèse ouverte par une chute doit aboutir immédiatement : le seul symbole qui sorte de cet état est surchauffe. L'automate reconnaît donc les journaux où une surchauffe suit directement une chute, les deux événements étant voisins.
Sur chute mesure surchauffe : après chute, deux états actifs, flux et chute vue ; puis mesure tue l'hypothèse, puisque chute vue n'a pas de transition pour mesure, et il ne reste que flux ; la surchauffe finale laisse flux. Mot rejeté, avec un seul état actif à la fin.
Sur mesure chute surchauffe : mesure laisse flux ; chute allume flux et chute vue ; surchauffe mène flux sur flux et chute vue sur motif trouvé, soit deux états actifs dont un acceptant. Mot accepté.
La comparaison des deux mots isole le rôle exact de la boucle sur chute vue : elle est ce qui autorise les événements intermédiaires, et donc ce qui distingue « plus tard » de « juste après ».
Un contrôle qualité veut détecter les journaux qui se terminent par une `surchauffe`. Écrire l'automate non déterministe correspondant, et dire combien d'états sont actifs pendant la lecture.
Le principe est celui du motif, mais l'hypothèse porte sur la fin : à chaque surchauffe lue, l'automate ouvre l'hypothèse « c'était la dernière ».
surchauffemesuresurchauffe
État actif : flux.
Deux états au plus sont actifs : flux, toujours, et dernier vu chaque fois qu'une surchauffe vient d'être lue. Sur surchauffe mesure surchauffe, le compte vaut 2 après le premier symbole, 1 après mesure, qui tue l'hypothèse puisque dernier vu n'a aucune transition sortante, et 2 de nouveau à la fin : le mot est accepté. Sur surchauffe mesure, il vaut 1 à la fin, et le mot est rejeté.
Cet automate tient en deux états parce qu'il n'a rien à mémoriser : l'hypothèse qu'il ouvre est confirmée par la fin du mot ou détruite par le symbole suivant.
Une vanne de sécurité se teste soit par une séquence courte, `ouvre` puis `ferme`, soit par une séquence longue, `ouvre`, `purge`, `ferme`. Écrire un automate qui accepte les deux avec une transition spontanée, et dire ce qui est allumé avant toute lecture.
La purge est une étape facultative placée au milieu : c'est exactement la situation du séchage. Une transition spontanée permet de la contourner sans dupliquer la fin de la séquence.
ouvreferme
État actif : fermée.
Avant toute lecture, un seul état est allumé, fermée : l'état initial n'a aucune transition spontanée sortante, donc sa fermeture spontanée se réduit à lui-même. Les deux états allumés apparaissent après ouvre, avec ouverte et prête.
La transition spontanée aurait aussi pu être placée au départ, en reliant un nouvel état initial à deux branches complètes ; le résultat serait le même langage, avec deux états de plus et une duplication du symbole ferme.
Vérification
1.Un automate a deux transitions étiquetées chute au départ du même état. Que fait-il en lisant chute ?
2.Après lecture complète d'un mot, trois états sont actifs et aucun n'est acceptant. Le mot est :
3.Que signifie une transition ε entre deux états ?
4.Sur l'automate du séchage facultatif, deux états s'allument après la lecture de lavage. Pourquoi ?
5.Dans l'automate du motif, que représente l'état chute vue lorsqu'il est allumé ?
6.L'ensemble des états actifs devient vide au milieu de la lecture. Que peut-on en conclure ?
7.Quel est l'intérêt principal d'un automate non déterministe pour l'ingénieur qui l'écrit ?
La méthode
- Repérer le non-déterminisme : chercher un état d'où partent deux transitions portant le même symbole, ou une transition
ε. La figure l'annonce d'elle-même dans son en-tête. - Partir de la fermeture spontanée de l'état initial, et non du seul état initial : des états peuvent être allumés avant toute lecture.
- Lire un symbole en collectant les destinations depuis tous les états actifs, puis appliquer la fermeture spontanée au résultat.
- Interpréter chaque état allumé comme une hypothèse encore vivante, et non comme une machine dupliquée.
- Conclure : accepté si un état acceptant est allumé à la fin du mot, rejeté sinon, et rejeté d'office si l'ensemble s'est vidé en route.
- Écrire un motif « X puis plus tard Y » avec une boucle sur l'état de départ, une transition vers un état d'attente, une boucle sur cet état d'attente, puis la transition de sortie.
- Écrire une étape facultative avec une transition spontanée qui la contourne, plutôt qu'en dupliquant la suite de l'automate.
Synthèse
- Un automate est non déterministe dès qu'un état porte deux transitions de même symbole, ou une transition spontanée
ε. - Son exécution manipule un ensemble d'états actifs : la figure les allume tous et annonce « N états actifs en même temps », ce qui rend l'exploration parallèle visible au lieu de la laisser imaginer.
- Chaque état allumé est une hypothèse sur ce qui a été lu ; une hypothèse meurt quand aucune transition ne la prolonge, et cela ne compromet pas les autres.
- Un mot est accepté dès qu'un seul chemin aboutit à un état acceptant ; il est rejeté quand aucun état acceptant n'est allumé à la fin, ou quand l'ensemble des états actifs s'est vidé.
- Une transition spontanée franchit un arc sans consommer de symbole ; la fermeture spontanée s'applique au départ et après chaque lecture, et peut allumer des états avant tout symbole lu.
- Chercher un motif noyé dans un flux s'écrit en trois lignes avec du non-déterminisme, là où la version déterministe demande de décider à la main ce que devient chaque symbole dans chaque état.
L'ensemble des états actifs est devenu la vraie donnée de l'exécution. Le chapitre sur la déterminisation en fait un état à part entière, et ramène la lecture à un seul état courant et à une case de tableau.