Reconnaître une séquence
Ce que ce chapitre apporte
- Nommer l'alphabet, les mots et le langage d'un problème de reconnaissance.
- Distinguer l'état initial des états acceptants, et lire le verdict d'une lecture.
- Vérifier qu'un automate est déterministe, et reconnaître un automate qui ne l'est pas.
- Compléter un automate par un état puits, pour qu'aucune lecture ne se bloque.
- Passer du diagramme à la table de transition, et de la table au diagramme.
Le chapitre sur les états et les événements décrivait un système qui réagit. Celui-ci lui pose une seule question, et se contente de sa réponse : cette séquence est-elle valide, oui ou non ? Une sonde qui surveille l'ouverture d'une connexion, un contrôle de saisie qui vérifie un numéro de lot, un analyseur qui trie des lignes de journal font exactement cela. La machine ne commande plus rien, elle juge, et le double cercle devient le verdict. La difficulté sera de ne laisser aucune situation sans réponse.
Une seule question posée à la machine
Une sonde placée sur un lien réseau observe les paquets échangés entre deux machines et doit signaler les ouvertures de connexion anormales. Elle ne pilote rien : elle regarde passer une suite de paquets et rend un verdict, valide ou non. C'est le même objet mathématique qu'au chapitre précédent, avec deux restrictions qui changent tout l'usage : la séquence est lue jusqu'au bout, et seule compte la situation atteinte à la fin.
L'alphabet est l'ensemble fini des symboles que la machine sait lire : ici, les types de paquets observés. Un mot est une suite finie de symboles : ici, une séquence de paquets. Le langage reconnu par l'automate est l'ensemble de tous les mots qu'il accepte : ici, l'ensemble des ouvertures de connexion conformes.
Le vocabulaire vient de la linguistique, et il peut égarer : un « mot » n'a rien de littéraire, c'est une séquence d'événements, de paquets, de caractères ou de codes. Un « langage » est une règle de validité, et rien d'autre. Le reste du module emploie ces trois termes parce qu'ils sont ceux du domaine, mais il s'agit toujours de séquences à valider.
La poignée de main TCP
Une connexion TCP s'ouvre par trois paquets, dans cet ordre et dans aucun autre : le client émet un SYN, le serveur répond un SYN-ACK, le client confirme par un ACK. Le module de réseaux les détaille dans le chapitre sur le transport et les noms ; ici, seul leur ordre compte.
L'alphabet a donc trois symboles, SYN, SYN-ACK et ACK, et le langage à reconnaître contient un seul mot : SYN SYN-ACK ACK. Un automate qui reconnaît ce langage aligne quatre situations.
SYNSYN-ACKACK
État actif : fermée.
La lecture se termine sur établie, qui porte le double cercle : le mot est accepté. Tant qu'il reste un symbole à lire, la figure ne dit rien, ni oui ni non, et c'est volontaire : un verdict ne se rend qu'une fois la séquence entière consommée.
L'état initial est celui d'où part toute lecture, désigné par la flèche d'entrée. Les états acceptants, dessinés par un double cercle, sont ceux où une lecture terminée vaut acceptation. Un mot est accepté quand sa lecture, menée jusqu'au dernier symbole, s'achève sur un état acceptant ; dans tous les autres cas il est rejeté.
La vraie difficulté : ce que l'automate fait des autres cas
La séquence SYN ACK est une ouverture anormale, celle d'un client qui confirme une connexion que le serveur n'a jamais acceptée. Une sonde doit la rejeter. Or l'automate ci-dessus ne la rejette pas proprement : il s'arrête.
SYNACK
État actif : fermée.
Après SYN, l'état actif est demande émise. Le symbole ACK n'y a aucune transition : plus aucun état n'est actif, la lecture s'interrompt au deuxième symbole sur trois. La figure porte d'ailleurs la mention « incomplet : une lecture peut se bloquer » dès son en-tête.
Le résultat final est correct, le mot est bien rejeté, mais le chemin ne l'est pas. Un automate incomplet transcrit en programme donne un code qui ne sait pas quoi faire, et c'est l'erreur la plus fréquente de tout ce module : la lecture tombe sur une transition absente, le programme lève une exception ou renvoie une valeur vide, et le lecteur croit à un bug alors que le modèle est simplement muet.
Un automate est déterministe quand, dans chaque état et pour chaque symbole, il existe au plus une transition. Il est complet quand, dans chaque état et pour chaque symbole, il en existe au moins une. Les deux ensemble donnent exactement une transition par état et par symbole : la lecture d'un mot est alors un chemin unique, et elle ne s'arrête jamais avant la fin.
L'état puits
Compléter un automate ne demande pas d'inventer des situations : toutes les transitions manquantes mènent au même endroit, un état d'où l'on ne revient pas et qui n'est pas acceptant. Cet état s'appelle état puits, et il signifie « la séquence est déjà invalide, la suite n'y changera rien ».
SYNACK
État actif : fermée.
La séquence SYN ACK est maintenant lue en entier : fermée, puis demande émise, puis rejet. Le verdict est le même qu'avant, le mot est rejeté, mais il est rendu après lecture complète, et la sonde sait pourquoi : la transition empruntée est celle qui mène au puits.
L'état rejet absorbe tout ce qui arrive après lui, par les boucles qui reviennent sur lui-même. La séquence SYN SYN-ACK ACK ACK, une confirmation répétée, y tombe elle aussi : saisir ce mot dans la figure fait passer l'état actif par établie avant de le voir basculer dans rejet au dernier paquet.
Définir une transition pour chaque symbole dans chaque état. Cinq états et trois symboles font quinze transitions, pas une de moins. Le dessin en montre huit seulement, parce que plusieurs symboles partagent la même flèche : demande émise -> rejet : SYN, ACK en porte deux à elle seule. Le compte se vérifie sur la table, pas sur le dessin.
La table de transition, seconde écriture du même objet
Un diagramme se lit bien tant qu'il tient sur une page. Au-delà, ou dès qu'il faut vérifier la complétude, la table de transition est plus sûre : une ligne par état, une colonne par symbole, et la case donne l'état d'arrivée. Une case vide est une transition manquante, et elle se voit immédiatement.
| État | SYN | SYN-ACK | ACK |
|---|---|---|---|
→ fermée | demande émise | rejet | rejet |
demande émise | rejet | demande acceptée | rejet |
demande acceptée | rejet | rejet | établie |
établie ✓ | rejet | rejet | rejet |
rejet | rejet | rejet | rejet |
La flèche marque l'état initial, la coche les états acceptants. Cette table contient exactement la même information que le diagramme précédent : quinze cases, quinze transitions, aucune vide. C'est cette écriture qui se transcrit directement en programme, et c'est elle qu'il faut remplir avant de dessiner quoi que ce soit sur un automate de plus de cinq états.
Un numéro de lot industriel
Deuxième exemple, plus proche d'un contrôle de saisie : un numéro de lot s'écrit deux lettres suivies de trois chiffres, comme AB123. L'alphabet devrait compter trente-six symboles, vingt-six lettres et dix chiffres. Aucun dessin ne le supporterait, et rien ne serait gagné : la règle ne distingue pas A de B.
L'alphabet se réduit donc à deux symboles, L pour une lettre quelconque et C pour un chiffre quelconque. Ce regroupement est une abstraction délibérée, et il faut savoir ce qu'il coûte : l'automate obtenu valide la forme du numéro, pas les valeurs autorisées. Un contrôle de la plage des chiffres se fait ailleurs.
LLCCC
État actif : début.
Le mot LLCCC est accepté. Le mot LLCC est rejeté, mais sans blocage : la lecture va jusqu'au bout et s'achève sur 2 chiffres, qui n'est pas acceptant. Ces deux façons de rejeter sont distinctes, et une seule est propre.
LLCCCC
État actif : début.
Avec LLCCCC, la lecture atteint valide au cinquième symbole, puis s'arrête : aucune transition ne part de valide. Un numéro trop long bloque l'automate au lieu d'être refusé. L'état puits corrige les deux défauts d'un coup.
LLCCCC
État actif : début.
Quatorze transitions pour sept états et deux symboles : la lecture de LLCCCC se termine dans rejet après avoir consommé les six symboles. La table correspondante tient en sept lignes, et sa dernière colonne se remplit presque entièrement de rejet, ce qui est la signature visuelle d'un automate de validation.
| État | L | C |
|---|---|---|
→ début | 1 lettre | rejet |
1 lettre | 2 lettres | rejet |
2 lettres | rejet | 1 chiffre |
1 chiffre | rejet | 2 chiffres |
2 chiffres | rejet | valide |
valide ✓ | rejet | rejet |
rejet | rejet | rejet |
Deux transitions pour un même symbole
Le déterminisme se perd facilement, et presque toujours par inadvertance. Voici un premier jet du même contrôle, écrit par quelqu'un qui hésitait entre deux formats de numéro, LLCCC et LCCC, et qui a tracé les deux départs.
LLCCC
État actif : début.
Dès le premier symbole, deux états s'allument en même temps : l'automate ne choisit pas, il suit les deux chemins à la fois, et la figure le dit en toutes lettres sous le dessin. C'est du non-déterminisme, et le mot LLCCC finit par être accepté parce qu'un des deux chemins mène à un état acceptant.
Ce comportement est commode à écrire et impossible à transcrire tel quel en programme : à la première lettre, aucun code ne saurait quelle transition suivre. La construction des sous-ensembles montre comment transformer automatiquement un tel automate en automate déterministe équivalent. Jusque-là, les automates construits ici sont déterministes, et cela se vérifie sur la table : aucune case ne contient deux états.
Exercices type
STXLONGOCTETOCTETETX
État actif : attente.
Une trame série valide commence par `STX`, porte un octet de longueur `LONG`, puis un ou plusieurs octets de données `OCTET`, et se termine par `ETX`. L'automate ci-dessus est-il déterministe ? Est-il complet ? Quelles séquences invalides bloquent la lecture au lieu d'être rejetées ?
Il est déterministe : dans chaque état, chaque symbole apparaît au plus une fois, et l'état corps ne fait pas exception, puisque OCTET et ETX y sont deux symboles différents.
Il n'est pas complet : l'alphabet compte quatre symboles, l'automate a quatre états, il faudrait seize transitions et le dessin n'en porte que quatre. Toute séquence qui présente un symbole inattendu bloque, par exemple STX ETX, une trame sans octet de longueur, ou LONG STX, qui bloque dès le premier symbole. Une trame tronquée comme STX LONG OCTET ne bloque pas : elle est lue en entier et rejetée, car corps n'est pas acceptant.
Le complètement consiste à envoyer vers un état rejet les douze transitions absentes, et à faire boucler rejet sur lui-même pour les quatre symboles.
STXETX
État actif : attente.
La boucle corps -> corps : OCTET mérite un mot : c'est elle qui autorise un nombre quelconque d'octets de données. Sans elle, il faudrait un état par longueur de trame, ce qui est impossible dès que la longueur n'est pas bornée.
Construire la table de transition d'un automate qui accepte les numéros de lot de la forme deux lettres, trois chiffres, **suivies éventuellement d'une lettre de version**, comme `AB123` ou `AB123C`. Alphabet réduit à `L` et `C`.
Il faut un état acceptant de plus, atteint depuis le premier par une lettre. Les deux états valide et version sont acceptants, ce qui traduit le « éventuellement » de l'énoncé : la lecture peut s'arrêter à l'un comme à l'autre.
| État | L | C |
|---|---|---|
→ début | 1 lettre | rejet |
1 lettre | 2 lettres | rejet |
2 lettres | rejet | 1 chiffre |
1 chiffre | rejet | 2 chiffres |
2 chiffres | rejet | valide |
valide ✓ | version | rejet |
version ✓ | rejet | rejet |
rejet | rejet | rejet |
LLCCCL
État actif : début.
Deux états acceptants ne compliquent rien : le verdict demande seulement que la lecture s'achève sur l'un d'eux. Le mot LLCCC reste accepté, LLCCCLL tombe dans le puits à la septième lecture.
Une sonde doit accepter aussi bien une ouverture de connexion complète `SYN SYN-ACK ACK` qu'un refus franc `SYN RST`. Quelles modifications faut-il apporter à l'automate de la poignée de main, et combien de transitions la table comptera-t-elle ?
L'alphabet passe à quatre symboles, puisque RST s'ajoute. Il faut un second état acceptant, refusée, atteint depuis demande émise par RST. Le reste des cases va au puits.
Six états et quatre symboles font vingt-quatre transitions dans la table, toutes obligatoires. Le dessin, lui, en montre bien moins, car les symboles qui mènent au même état se regroupent sur une seule flèche.
SYNRST
État actif : fermée.
La séquence SYN SYN-ACK RST, une connexion coupée après acceptation, tombe dans le puits : elle n'est ni une ouverture réussie, ni un refus franc, et la sonde la signale. Décider si ce classement convient relève de la spécification, pas de l'automate : c'est le genre de question que la table rend visible en obligeant à remplir chaque case.
Vérification
1.Quand un automate rend-il son verdict sur un mot ?
2.Qu'est-ce qu'un automate complet ?
3.Un automate a 5 états et un alphabet de 3 symboles. Combien de transitions sa table compte-t-elle s'il est déterministe et complet ?
4.À quoi sert un état puits ?
5.Deux transitions portent le même symbole depuis le même état. Que montre la figure à la lecture de ce symbole ?
6.Sur l'automate de validation du numéro de lot complété, où se termine la lecture de LLCCCC ?
7.Que perd-on en réduisant l'alphabet d'un contrôle de saisie à L et C ?
La méthode
- Écrire l'alphabet en premier, et le garder fini et court : regrouper les symboles que la règle ne distingue pas, en notant ce que ce regroupement abandonne.
- Formuler le langage en une phrase qui commence par « les séquences telles que », avant de dessiner quoi que ce soit.
- Tracer le chemin d'un mot valide, d'un bout à l'autre : il donne la colonne vertébrale de l'automate et ses premiers états.
- Marquer l'état initial et les états acceptants, puis vérifier qu'aucun mot invalide ne s'achève sur un état acceptant.
- Remplir la table de transition, une ligne par état, une colonne par symbole, et envoyer vers un état puits toute case restée vide.
- Éprouver l'automate sur trois familles de mots : un mot valide, un mot trop court, un mot trop long ou contenant un symbole inattendu.
Synthèse
- Un automate reconnaisseur répond à une seule question : le mot lu en entier finit-il sur un état acceptant ?
- L'alphabet est l'ensemble fini des symboles lisibles, un mot une suite finie de symboles, le langage l'ensemble des mots acceptés.
- Déterministe veut dire au plus une transition par état et par symbole ; complet, au moins une ; les deux réunis donnent exactement une, et la lecture ne se bloque jamais.
- L'état puits reçoit toutes les transitions manquantes, n'est jamais acceptant et boucle sur lui-même : il transforme un blocage en rejet propre.
- La table de transition dit la même chose que le diagramme, en rendant visible la case vide que le dessin cache, et c'est elle qui se transcrit en programme.
- Le non-déterminisme se reconnaît à plusieurs états allumés en même temps ; la façon de s'en débarrasser est la construction des sous-ensembles.
Ces automates se dessinent encore à la main, un état après l'autre. Le chapitre sur les expressions régulières donne l'écriture d'une ligne qui décrit la même règle, et la construction mécanique qui en tire l'automate.