Ce qu'un automate ne sait pas faire
Ce que ce chapitre apporte
- Construire un automate qui vérifie l'équilibre entre deux événements, et observer exactement où il se bloque.
- Expliquer pourquoi ajouter des états ne repousse la limite que d'un cran.
- Repérer le moment où le jeton repasse par un état déjà visité, et dire ce que la machine vient d'oublier.
- Nommer les vérifications qu'aucune expression régulière ne fera jamais : parenthésage, blocs imbriqués, JSON, XML, HTML.
- Construire un automate par assemblage plutôt qu'à la main : complément, union, intersection.
Les chapitres précédents ont montré ce qu'un automate fini sait faire, et il en sait beaucoup : reconnaître une séquence, valider une trame, se déterminiser, se minimiser, se lire comme une expression régulière. Reste la question qu'un ingénieur finit toujours par poser devant un outil : où est la limite, et comment la reconnaître avant d'avoir passé trois jours à contourner l'incontournable.
Cette limite tient en une phrase : un automate à n états ne sait pas compter au-delà de n. Elle ne se démontre pas au tableau, elle se voit sur une figure. Ce chapitre la fait apparaître, en tire la conséquence la plus coûteuse en entreprise, puis montre ce qu'un automate sait encore faire très bien : se combiner à un autre.
Une règle simple, et un automate qui n'y arrive pas
Un superviseur de ligne reçoit deux événements : l'ouverture d'un lot et sa clôture. La règle de contrôle est de celles qu'un responsable qualité écrit en une ligne : à la fin de la journée, autant de clôtures que d'ouvertures. Rien de plus, pas d'ordre imposé, pas de délai.
Cette règle se ramène à un alphabet de deux symboles, et la convention vaut pour tout le chapitre : o note l'ouverture d'un lot, c sa clôture. Deux lettres plutôt que deux mots, parce que la démonstration porte sur la longueur des séquences et qu'il faudra en écrire de longues ; le langage à reconnaître est celui des journées qui comptent autant de c que de o.
Un premier automate mémorise l'écart entre les deux compteurs. L'état égal signifie « autant de clôtures que d'ouvertures », o1 signifie « une ouverture de plus », o2 « deux ouvertures de plus », et symétriquement c1 et c2 du côté des clôtures. Cinq états, donc cinq écarts mémorisables.
oocc
État actif : égal.
Avec oocc, le jeton passe par o1, o2, o1, puis revient sur égal : le mot est accepté, et il le mérite. Avec ccoo, le trajet est le même de l'autre côté du cercle, et le verdict aussi. L'automate est déterministe, et la légende de la figure signale qu'il est incomplet : certaines lectures peuvent se bloquer. C'est précisément ce qui va se produire.
oooccc
État actif : égal.
Le mot oooccc compte trois ouvertures et trois clôtures : il est correct, et il devrait être accepté. Au troisième o, la figure affiche « plus aucun état actif : la lecture se bloque, et le mot est rejeté sans être lu en entier ». L'automate n'a pas d'état pour « trois ouvertures de plus » ; il n'a donc rien à répondre, et il refuse une journée parfaitement conforme.
Ajouter des états ne règle rien
La réaction naturelle consiste à agrandir la machine. Sept états au lieu de cinq, pour mémoriser un écart allant jusqu'à trois de chaque côté.
oooocccc
État actif : égal.
Le mot oooccc passe maintenant sans encombre. Mais oooocccc, quatre lots ouverts avant la première clôture, bloque au quatrième o. La limite a reculé d'un cran, elle n'a pas disparu.
Le raisonnement se généralise sans effort. Un automate qui accepte le langage doit distinguer les écarts 0, 1, 2, 3, et ainsi de suite : à chaque écart possible il faut un état différent, sinon deux écarts différents sont mémorisés par le même état, et la machine les confond. Comme un automate fini a un nombre d'états fixé une fois pour toutes, et que l'écart, lui, n'est borné par rien, aucun nombre d'états ne suffit.
Un automate ne dispose d'aucune variable, d'aucun compteur, d'aucun bloc-notes. Entre deux symboles, tout ce qu'il a retenu de ce qu'il a lu tient dans le nom de l'état où il se trouve. Un automate à n états sait donc distinguer au plus n situations, et pas une de plus.
Le jeton repasse forcément par un état déjà visité
L'argument précédent reste une intuition tant qu'il n'est pas vu. Il le devient dès que l'on tente de supprimer le blocage plutôt que d'agrandir la machine.
Puisque o2 n'a pas de transition sur o, il suffit de lui en donner une. La plus simple referme le cycle : depuis o2, un o de plus ramène sur égal. Symétriquement pour c2. L'automate devient complet : plus aucune lecture ne se bloque, et la figure ne signale plus rien.
ooo
État actif : égal.
Le mot ooo compte trois ouvertures et aucune clôture. La figure l'annonce pourtant accepté. La raison se lit sur le dessin : après trois o, le jeton est revenu sur égal, exactement là où il était avant de commencer.
Nombre de o lus | État atteint |
|---|---|
| 0 | égal |
| 1 | o1 |
| 2 | o2 |
| 3 | égal |
| 4 | o1 |
| 5 | o2 |
La troisième ligne est celle qui coûte cher. À partir de là, l'automate est dans la même situation qu'au départ : quoi qu'il lise ensuite, il répondra ce qu'il aurait répondu si la lecture avait commencé à cet instant. Dans la figure, oooccc et ccc reçoivent donc le même verdict, acceptés tous les deux, alors que le premier respecte la règle et que le second la viole de trois clôtures.
Ranger n + 1 objets dans n tiroirs oblige à en mettre deux dans le même tiroir. Ici, les tiroirs sont les états et les objets sont les positions du jeton.
Un automate à n états qui lit un mot de n symboles occupe n + 1 positions successives, en comptant celle du départ. Deux d'entre elles au moins sont le même état. Appeler k et m les deux rangs concernés, avec k < m : après avoir lu k symboles et après en avoir lu m, la machine est au même endroit, donc dans le même état de mémoire. Tout ce qui suit lui fera suivre le même chemin et rendre le même verdict.
Il ne reste plus qu'à en tirer la contradiction, et elle tient en trois lignes. Soit un automate à n états quelconque, censé reconnaître les mots comptant autant de o que de c. Lui faire lire n fois la lettre o : deux rangs k < m partagent le même état. Lui faire lire ensuite m fois la lettre c. Le mot complet est soit o répété m fois suivi de c répété m fois, qui respecte la règle, soit o répété k fois suivi de c répété m fois, qui la viole puisque k est plus petit que m. Ces deux lectures arrivent au même état et reçoivent le même verdict : l'automate se trompe forcément sur l'une des deux.
Elle ne dit pas qu'un automate est incapable de compter. Compter jusqu'à trois, jusqu'à mille, jusqu'à un million : un automate le fait, au prix d'un état par valeur. Elle dit qu'il est incapable de compter sans borne connue à l'avance. Un contrôle qui accepte une profondeur maximale de dix blocs imbriqués est parfaitement réalisable ; un contrôle qui accepte toutes les profondeurs ne l'est pas.
Ce que cela interdit, sur le terrain
Le chapitre sur les expressions régulières a montré comment toute expression se compile en automate, brique par brique. La réciproque est vraie également : tout automate fini se réécrit en expression régulière. Les deux écritures décrivent donc exactement les mêmes langages, et la limite qui vient d'être démontrée pour les automates vaut, mot pour mot, pour les expressions régulières.
Vérifier que des parenthèses, des accolades ou des balises sont correctement imbriquées revient exactement à vérifier qu'il y a autant d'ouvertures que de fermetures, dans le bon ordre. C'est le langage qui vient d'être déclaré hors de portée.
En découlent quatre impossibilités, rencontrées presque chaque année dans un projet :
- aucune expression régulière ne valide du JSON ;
- aucune expression régulière ne valide du XML ;
- aucune expression régulière ne valide du HTML ;
- aucune expression régulière ne valide une expression arithmétique parenthésée.
Non pas « c'est difficile », non pas « il faut une expression très longue » : c'est impossible, et aucune quantité de travail n'y changera rien.
Le piège est d'autant plus efficace que la version bornée fonctionne. Un fichier de configuration d'équipement réseau s'écrit en blocs imbriqués, ouverts par { et refermés par }. Un automate à trois états contrôle l'imbrication jusqu'à la profondeur deux.
{{{}}}
État actif : niveau0.
Avec {{}}, deux niveaux, le contrôle passe et le mot est accepté. Avec {{{}}}, la lecture se bloque au troisième {. Le contrôleur ne dit pas « je ne sais pas faire » : il dit « configuration invalide ». Une équipe qui teste son outil sur des fichiers à deux niveaux le déclare bon, et découvre le défaut le jour où un équipement plus complexe arrive en production.
Une structure imbriquée se traite avec un analyseur, pas avec une expression régulière : la bibliothèque json pour du JSON, un analyseur XML pour du XML, un analyseur HTML pour du HTML. Ces outils existent dans tous les langages, ils sont testés depuis des années, et ils s'appuient sur une mémoire que l'automate n'a pas.
L'expression régulière reste excellente pour ce qui est plat : extraire un code postal, valider un identifiant d'équipement, découper une ligne de journal en champs. Le partage se fait sur une seule question : la structure à reconnaître contient-elle des imbrications de profondeur non bornée ?
Assembler plutôt que redessiner
La limite étant posée, reste une bonne nouvelle, et elle est très utile en pratique. Les langages reconnus par un automate fini sont stables par combinaison : combiner deux automates redonne un automate, et la construction est mécanique. Un besoin de contrôle qui se formule avec « et », « ou » ou « sauf » n'a donc pas à être dessiné à la main.
Le complément : inverser les acceptants
Voici un automate de validation de trames, sur un protocole à trois messages : debut, donnee, fin. Une trame valide commence par debut, contient un nombre quelconque de donnee, et se termine par fin. L'état rebut est l'état puits, celui qui absorbe tout ce qui ne convient pas.
debutdonneefin
État actif : attente.
La trame debut donnee fin est acceptée. La trame tronquée debut donnee est rejetée : la lecture se termine dans corps, qui n'est pas acceptant.
Pour construire l'automate qui accepte exactement les trames invalides, il est inutile de recommencer le dessin. Il suffit d'échanger les rôles : ce qui était acceptant ne l'est plus, ce qui ne l'était pas le devient.
debutdonnee
État actif : attente.
Les transitions sont identiques au caractère près ; seule la ligne finaux: a changé. La trame tronquée debut donnee est maintenant acceptée, et la trame complète debut donnee fin est rejetée. Ce second automate est le détecteur d'anomalies correspondant au premier, obtenu sans une seule décision de conception.
Inverser les acceptants d'un automate incomplet ne donne pas le complément : un mot qui bloquait est rejeté par les deux automates, et se retrouve donc refusé des deux côtés. Inverser les acceptants d'un automate non déterministe ne le donne pas davantage, puisqu'un mot peut avoir à la fois un chemin acceptant et un chemin non acceptant.
L'ordre des gestes est donc : déterminiser, compléter avec un état puits, puis inverser. C'est là que l'état puits, souvent perçu comme une formalité, devient indispensable.
L'union : un nouvel état initial et deux transitions spontanées
Un équipement accepte deux formes d'échange : une trame de données, comme ci-dessus, ou un simple test de liaison, test suivi de reponse. Il faut un automate qui accepte l'une ou l'autre.
La construction tient en deux transitions spontanées. Un nouvel état initial est ajouté, relié par ε aux deux états initiaux d'origine, et les états acceptants des deux automates restent acceptants.
testreponse
3 états actifs en même temps : depart, trame0, liaison0. L'automate suit tous les chemins à la fois.
Avant toute lecture, la figure annonce trois états actifs : depart, trame0 et liaison0. Les transitions spontanées ont allumé les deux points de départ à la fois, et la machine attend les deux formes d'échange en parallèle. Au premier symbole lu, l'une des deux branches s'éteint : avec test, il ne reste que la branche du test de liaison, qui accepte au symbole suivant.
Le résultat est non déterministe, et ce n'est pas un défaut : la construction des sous-ensembles le déterminise ensuite, mécaniquement. Dessiner directement l'automate déterministe de l'union serait un travail bien plus long, et bien plus facile à rater.
L'intersection : le produit des deux automates
Deux règles doivent tenir en même temps sur un journal de maintenance, dont les événements sont demarrage, arret et alerte :
- le journal contient au moins une
alerte; - le dernier événement du journal est un
arret.
Chaque règle se surveille à part, avec deux états. La première machine part de sansAlerte et passe définitivement à avecAlerte au premier alerte. La seconde part de finAutre, va sur finArret à chaque arret, et retombe sur finAutre à chaque demarrage et à chaque alerte.
Surveiller les deux règles d'un seul parcours revient à faire tourner les deux machines côte à côte : un état du produit est le couple des deux états courants. Sa table se remplit couple par couple, comme la table des sous-ensembles de la déterminisation, à ceci près qu'une case ne se calcule pas, elle se lit deux fois, une moitié dans chaque machine.
| Couple d'états | Nom | demarrage | arret | alerte |
|---|---|---|---|---|
→ (sansAlerte, finAutre) | depart | (sansAlerte, finAutre) | (sansAlerte, finArret) | (avecAlerte, finAutre) |
(sansAlerte, finArret) | arretOK | (sansAlerte, finAutre) | (sansAlerte, finArret) | (avecAlerte, finAutre) |
(avecAlerte, finAutre) | alerteVue | (avecAlerte, finAutre) | (avecAlerte, finArret) | (avecAlerte, finAutre) |
(avecAlerte, finArret) ✓ | lesDeux | (avecAlerte, finAutre) | (avecAlerte, finArret) | (avecAlerte, finAutre) |
La première ligne part du couple des deux états initiaux : c'est la seule qui ne naisse pas d'une autre. Sur demarrage, la première moitié reste sur sansAlerte et la seconde sur finAutre, puisque le dernier événement n'est toujours pas un arrêt : couple inchangé, donc une boucle. Sur arret, la première moitié ne bouge pas davantage et la seconde passe sur finArret : le couple (sansAlerte, finArret) n'existait pas encore, il ouvre une ligne et reçoit le nom arretOK. Sur alerte, la première moitié bascule sur avecAlerte pendant que la seconde retombe sur finAutre : nouveau couple encore, nommé alerteVue.
La deuxième ligne se lit de la même façon et montre ce que la construction a de mécanique. Depuis (sansAlerte, finArret), un demarrage laisse la moitié gauche en place et ramène la droite sur finAutre : le couple obtenu est celui de la première ligne, aucune ligne nouvelle n'apparaît. Un arret maintient la moitié droite sur finArret, c'est une boucle. Un alerte fait basculer la gauche et retomber la droite, ce qui redonne (avecAlerte, finAutre), déjà écrit à la ligne précédente. Aucune décision n'a été prise nulle part : chaque moitié suit sa propre machine, et le couple obtenu est cherché parmi les lignes déjà là.
Les deux dernières lignes vont plus vite, parce que la moitié gauche n'y bouge plus : une alerte vue reste vue, et les trois colonnes ne font plus que déplacer la moitié droite. C'est la ligne alerteVue qui donne enfin le couple acceptant, dans sa colonne arret. Le tableau se referme alors sur quatre lignes, faute de couple nouveau à explorer : deux états par machine, quatre couples, pas un de plus.
Un couple n'est acceptant que si ses deux moitiés le sont, donc seul (avecAlerte, finArret), c'est-à-dire lesDeux, l'est. Chaque ligne du tableau devient un état du dessin ci-dessous, et chaque case une flèche.
demarragealertedemarragearret
État actif : depart.
Le journal proposé est accepté : une alerte est bien présente, et le dernier événement est un arrêt. En retirant l'alerte, demarrage demarrage arret, la lecture se termine dans arretOK et le journal est rejeté. En terminant par un démarrage, demarrage alerte arret demarrage, elle se termine dans alerteVue et le journal est rejeté aussi.
| Combinaison | Construction | Coût en états |
|---|---|---|
| Complément, « tout sauf » | déterminiser, compléter, inverser les acceptants | inchangé |
| Union, « l'un ou l'autre » | un état initial de plus, deux transitions spontanées | n + m + 1 |
| Intersection, « l'un et l'autre » | le produit : un état par couple d'états | n × m au plus |
Ces trois constructions sont la raison pour laquelle un outil comme un pare-feu ou un analyseur de journaux peut compiler une liste de règles hétéroclites en une seule machine qui les vérifie toutes d'un seul parcours.
Ce qu'il faudrait de plus
Le contrôleur de blocs imbriqués donne la mesure exacte de ce qui manque. Avec cinq états, il tient la profondeur quatre.
{{{{}}}}
État actif : niveau0.
Le dessin est une chaîne, et chaque niveau supplémentaire coûte un état de plus. Pour accepter toutes les profondeurs, il faudrait une chaîne infinie : ce n'est plus un automate fini.
Ce qui manque n'est pas de la place, c'est une mémoire d'appoint, extérieure aux états. La bonne structure porte un nom connu du parcours d'algorithmique : une pile. Empiler un jeton à chaque {, en dépiler un à chaque }, refuser si la pile est vide au moment de dépiler, et exiger qu'elle soit vide à la fin. Quatre gestes, une profondeur illimitée, et zéro état supplémentaire.
La machine obtenue en ajoutant une pile à un automate fini s'appelle un automate à pile, et elle reconnaît précisément les structures imbriquées qui viennent d'être déclarées hors de portée. Elle sort du cadre de ce module, mais elle explique l'organisation de tous les outils qui lisent du texte structuré : une première passe plate, confiée à un automate fini, découpe le flux en mots ; une seconde passe, confiée à une machine à pile, vérifie l'imbrication. Le chapitre sur l'implémentation reste du côté plat, celui qui se code en trente lignes.
Exercices type
donnee
État actif : attente.
L'automate ci-dessus prétend accepter exactement les trames invalides du protocole `debut`, `donnee`, `fin`. Le mot `donnee` n'est pas une trame valide : il devrait donc être accepté. Que se passe-t-il, et quel geste a été oublié ?
La figure affiche « plus aucun état actif : la lecture se bloque ». Le mot donnee est donc rejeté, alors qu'il aurait dû être accepté.
L'automate de départ était incomplet : depuis attente, aucune transition ne portait donnee. Inverser les acceptants n'a rien changé à cette absence, et un mot qui bloquait chez l'un bloque chez l'autre. Résultat : donnee est refusé par l'automate des trames valides et par son prétendu complément, ce qui est contradictoire.
Le geste oublié est la complétion : ajouter l'état puits rebut, y diriger toutes les transitions manquantes, et le rendre acceptant dans le complément. C'est exactement l'automate à quatre états de la section sur le complément, où rebut figure bien parmi les acceptants.
L'ordre à retenir : déterminiser, compléter, puis seulement inverser.
oooo
État actif : r0.
Cet automate à quatre états est proposé pour reconnaître les mots comptant autant de `o` que de `c`. Il accepte déjà `oooo`, qui compte quatre `o` et aucun `c`. Donner un mot de six symboles qu'il classe mal, et dire en une phrase ce que la machine a oublié.
Le mot oooooc, cinq o et un c, est accepté alors que les deux compteurs diffèrent de quatre. Le trajet est r0, r1, r2, r3, r0, r1, puis retour sur r0 par le c final.
Ce que la machine a oublié : après quatre o, le jeton est revenu sur r0, c'est-à-dire exactement là où il se trouvait avant la première lecture. Les mots oooo et le mot vide sont donc, pour elle, indiscernables : tout ce qui suit leur vaudra le même verdict.
Cet automate ne compte pas l'écart, il compte l'écart modulo quatre. C'est la seule chose qu'un nombre fini d'états permette de faire sans se bloquer, et c'est insuffisant : oooo et le mot vide ont le même reste, sans avoir le même écart.
Un collègue annonce qu'il a « presque fini » l'expression régulière qui valide les fichiers XML de configuration reçus des fournisseurs : il lui reste à gérer les balises imbriquées. Que lui répondre, et que proposer ?
L'expression ne sera jamais finie, et le temps passé dessus est perdu. Une balise ouvrante doit être refermée, les balises s'imbriquent à une profondeur qu'aucun format XML ne borne, et vérifier cette imbrication revient à compter les ouvertures non encore refermées. Un automate fini, donc une expression régulière, ne sait compter que jusqu'à une borne fixée d'avance par son nombre d'états.
Le détour habituel, « écrire une expression qui gère jusqu'à dix niveaux », produit une expression illisible qui reste fausse : elle refuse un fichier valide au onzième niveau, et elle le refuse en annonçant « fichier invalide », ce qui est un mensonge.
Ce qu'il faut proposer : un analyseur XML, disponible dans la bibliothèque standard de tous les langages courants. Il lit le fichier, signale l'endroit exact d'une balise non refermée, et gère l'imbrication avec la pile que l'expression régulière n'a pas.
Reste une place pour l'expression régulière, en amont ou en aval : contrôler qu'une valeur extraite est bien une référence d'article ou une date. Ces contrôles-là sont plats, et ils sont son terrain.
Vérification
1.Pourquoi un automate à cinq états ne peut-il pas reconnaître les mots comptant autant de o que de c ?
2.Un automate à sept états lit un mot de sept symboles. Que peut-on affirmer sur son trajet ?
3.Un automate revient, après avoir lu ooo, sur l'état où il était avant toute lecture. Quelle conséquence ?
4.Quelle vérification une expression régulière ne pourra jamais faire ?
5.Quel est l'ordre correct des gestes pour construire l'automate du complément ?
6.Comment construire l'automate qui accepte le langage de A ou celui de B ?
7.Deux automates ont respectivement 4 et 5 états. Combien d'états au plus a l'automate de leur intersection ?
8.Que faudrait-il ajouter à un automate fini pour vérifier une imbrication de profondeur quelconque ?
La méthode
- Poser la question du comptage devant tout besoin de reconnaissance : le contrôle demande-t-il de retenir un nombre que rien ne borne ? Si oui, aucun automate fini, donc aucune expression régulière, ne le fera.
- Chercher l'imbrication : parenthèses, accolades, balises, blocs, structures qui se contiennent elles-mêmes. C'est la forme sous laquelle le comptage non borné se présente presque toujours.
- Soumettre un automate suspect au test du retour en lui faisant lire le même symbole autant de fois qu'il a d'états : si le jeton revient sur un état déjà visité, écrire les deux mots qu'il ne distingue plus et vérifier leur verdict.
- Se rabattre sur un analyseur dès qu'une imbrication est en jeu, et réserver l'expression régulière aux contrôles plats, sur lesquels elle est imbattable.
- Construire par assemblage : pour « sauf », déterminiser, compléter, inverser les acceptants ; pour « ou », un état initial neuf et deux transitions spontanées ; pour « et », le produit, un état par couple.
- Déterminiser le résultat de l'assemblage si une exécution rapide est recherchée, et le minimiser pour en retrouver la taille utile.
Synthèse
- Un automate à
nétats ne retient quensituations : sa seule mémoire est son état courant, et aucun compteur ne l'accompagne. - Le langage des mots comptant autant de
oque decest hors de portée de tout automate fini, parce qu'il demanderait un état par écart possible. - Le principe des tiroirs rend la limite visible : sur un mot de
nsymboles, un automate ànétats repasse forcément par un état déjà visité, et il ne distingue plus les deux préfixes concernés. - Conséquence directe : aucune expression régulière ne valide un parenthésage, ni du JSON, ni du XML, ni du HTML. Ces structures se traitent avec un analyseur.
- Les langages reconnus par un automate sont stables par complément, union et intersection : « sauf » s'obtient en inversant les acceptants d'un automate déterministe et complet, « ou » par deux transitions spontanées, « et » par le produit.
- Lever la limite demande une mémoire d'appoint, une pile, et non des états supplémentaires, qui ne repoussent la borne que d'un cran.
La limite étant posée, il reste à faire tourner ce qui tient dans le cadre : le chapitre sur l'implémentation transcrit la table de transition en une trentaine de lignes de Python, et referme le module sur un outil exécutable.