Une machine qui répond seulement oui ou non
Un automate fini est une machine très simple qui lit un mot lettre par lettre, puis répond oui ou non. Il sert à vérifier un texte en n’utilisant presque aucune mémoire.
Le portique d’une station de métro en est un exemple : il est fermé ou ouvert, et chaque ticket ou chaque passage change son état. Vous allez apprendre à suivre un automate fini à la main, puis à le programmer.
À la fin de cette leçon
Remarque
Je peux suivre un automate fini sur un mot et dire si ce mot est accepté.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Automate fini | une machine à états qui lit un mot lettre par lettre | |
| État | ce dont la machine se souvient à un instant | PAIR |
| Transition | le passage d’un état à un autre quand elle lit une lettre | |
| État initial | l’état où la machine commence | |
| État final | un état qui fait accepter le mot | |
| Mot accepté | un mot qui se termine sur un état final |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Un automate retient un état, pas le mot
Un automate fini lit un mot lettre par lettre, de gauche à droite. Il ne garde en mémoire qu’un seul état à la fois.
À chaque lettre, il suit une transition : selon son état et la lettre lue, il passe dans un nouvel état. Au début, il est dans l’état initial. Voici un exemple : un automate qui accepte les mots binaires ayant un nombre pair de 1.
Exemple travaillé : la table des transitions
| État | Si la lettre est 0 | Si la lettre est 1 | Rôle |
|---|---|---|---|
| PAIR | PAIR | IMPAIR | Initial et final |
| IMPAIR | IMPAIR | PAIR | Ni initial, ni final |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Suivre l’automate de la parité
# Un automate qui compte la parité du nombre de 1.
table = {
"PAIR": {"0": "PAIR", "1": "IMPAIR"},
"IMPAIR": {"0": "IMPAIR", "1": "PAIR"},
}
etat = "PAIR"
mot = "1101"
for lettre in mot:
etat = table[etat][lettre]
print("lu", lettre, "-> état", etat)
if etat == "PAIR":
print("mot accepté")
else:
print("mot refusé")
# Remplacez le mot par "1001", puis relancez.
Accepté si l’on finit sur un état final
Un mot est accepté si l’automate termine sur un état final. Sinon, il est refusé. Le mot vide, sans aucune lettre, est accepté seulement si l’état initial est aussi final.
Si une lettre n’a aucune transition dans l’état courant, l’automate s’arrête et refuse le mot. On peut aussi imaginer un état poubelle, dont on ne sort plus, qui reçoit toutes les lettres interdites.
Exemple travaillé : les mots qui finissent par ab
| État | Si la lettre est a | Si la lettre est b | Rôle |
|---|---|---|---|
| DEBUT | A_VU | DEBUT | Initial |
| A_VU | A_VU | AB_VU | On vient de lire a |
| AB_VU | A_VU | DEBUT | Final : on vient de lire ab |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La lecture du mot abab, pas à pas
| Étape | Lettre lue | État avant | État après |
|---|---|---|---|
| 1 | a | DEBUT | A_VU |
| 2 | b | A_VU | AB_VU |
| 3 | a | AB_VU | A_VU |
| 4 | b | A_VU | AB_VU, final : mot accepté |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
grep décide comme un automate
Les outils qui cherchent du texte, comme grep, sont construits sur des automates. L’option -E donne un motif, et -x demande que toute la ligne convienne.
Le motif 0*(10*10*)* veut dire : des 0, puis des paires de 1 séparées par des 0. Il accepte donc les mêmes mots que l’automate de la parité. Vous étudierez ces motifs dans la leçon suivante.
Les mots acceptés
printf '%s\n' 1101 1001 0 11 | grep -E -x '0*(10*10*)*'Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Les mots refusés
printf '%s\n' 1101 1001 0 11 | grep -E -x -v '0*(10*10*)*'Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Un seul bit de mémoire suffit
python3 -c "print('1101'.count('1') % 2)"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Erreur fréquente
Attention
Beaucoup de gens pensent qu’un automate se souvient de tout le mot lu, ou qu’il peut compter sans limite. Il n’a qu’un nombre fini d’états : il retient seulement ce que ses états distinguent. Savoir si le nombre de 1 est pair ne demande qu’un bit. Comparer deux nombres aussi grands qu’on veut demande plus que tout nombre fixé d’états.
Pour aller plus loin
Dessinez un automate sur l’alphabet a et b qui accepte les mots contenant au moins un a. Combien d’états faut-il ?
Écrivez sa table, puis testez-la avec la fonction de la leçon. Vérifiez que le mot vide est refusé.