Bonjour à tous ! Aujourd’hui un article un peu différent puisque nous allons nous intéresser à une part importante de l’informatique théorique : les automates.
Depuis environ un mois, j’ai commencé à donner des TDs sur la théorie des langages et les automates et je me suis rendu compte que beaucoup d’étudiants avaient des difficultés avec le cours qui est parfois un peu trop formel.
L’idée de cette série d’articles sur les automates est de proposer une approche plus concrète de la découverte des automates, en développant en parallèle une implémentation en Python (qui est disponible sur ce dépot). Notez que ce cours se concentrera sur les opérations et algorithmes associés aux automates et par conséquent ne pourra pas se substituer à un cours académique sur la théorie des langages. Plus particulièrement, les démonstrations mathématiques associées seront absentes et sont de toute façon accessibles simplement sur le net.
Cette série d’article s’étalera certainement sur plusieurs mois, proposant parfois des exemples et des exercices, tout en montrant une implémentation possible. Voici le plan de cette série, qui sera peut-être amené à changer :
- Introduction aux automates : définition d’un automate a états fini déterministe et présentation de quelques exemples.
- Implémentation d’un AFD : implémentation d’une API de manipulation d’automate en Python.
- Opérations et notions élémentaires : notions de successeur/prédécesseur, d’accessibilité, d’automate émondé et d’automate complet.
- Négation et produit d’automate.
- Distingabilité et minimisation.
- Les automates à états finis non déterministes (AFND) : algorithme de déterminisation.
- Les AFND avec ε-transitions.
Qu’est-ce qu’un automate ?
Pour l’expliquer simplement, un automate est une machine abstraite prenant en entrée un mot, c’est à dire une séquence finie de symboles, et qui donne un résultat binaire : accepté ou refusé.
Ci-suit la représentation graphique d’un automate acceptant les mots contenant au moins une fois le symbole a sur l’alphabet “ab” :
Mais comment ça fonctionne ? L’idée va être de suivre les transitions en fonction des symboles d’un mot.
On démarre à l’état initial (qui est ici l’état 0, comme le montre la flèche incidente) et, pour chaque symbole du mot, on se déplace d’état en état en fonction des transitions. Si on termine sur un état final (indiqué par un double cercle) le mot est accepté, sinon le mot est refusé. Prenons l’exemple du mot bbab :
- On démarre à l’état initial 0.
- Le premier symbole est b, on reste à l’état 0.
- Le symbole suivant est a, on va à l’état 1.
- Le symbole suivant est b, on reste à l’état 0.
- Le dernier symbole est b, on reste à l’état 1.
- Nous sommes sur un état final (1), le mot est accepté.
Vous pouvez vous amuser à exécuter plusieurs mots (a, b, bbbbb, aaaaab…), et vous constaterez qu’effectivement, tous les mots contenant au moins un a sont acceptés. C’est assez évident dans cet exemple puisqu’on rejoint l’état final 1 dès l’instant où on rencontre un a. Nous verrons d’autres exemples d’automates dans la suite de l’article.
Définitions
Plus formellement, un automate est défini par le quintuplet (Q, q0, Σ, δ, F), avec :
- Q, l’ensemble des états.
- q0, l’état initial.
- Σ, l’alphabet.
- δ, la fonction de transition.
- F, l’ensemble des états finaux (accepteurs).
L’alphabet Σ correspond simplement à l’ensemble des symboles possibles. Dans l’exemple précédant l’alphabet était ab, mais on peut travailler sur toute sorte de symboles.
Q est l’ensemble des états de l’automate. Dans l’exemple précédent il contient l’état 0 et l’état 1. On a un unique état final q0 ∈ Q et un ensemble d’états finaux F ⊆ Q. Ici, F contient uniquement l’état 0.
La fonction de transition δ est un peu plus difficile à comprendre. En fait, c’est un moyen de représenter l’ensemble des transitions de l’automate. δ : Q x Σ →Q , associe un état à un symbole et un état donné. Dans l’exemple précédent on a δ = {(0, a, 1), (0, b, 0), (1, a, 1), (1, b, 1)}.
Notez qu’il n’est pas nécessaire que la fonction de transition soit totale, c’est-à-dire qu’une transition soit définie pour chaque symbole et chaque état. Si on exécute un mot et qu’on n’a pas de transition pour un symbole donné, alors l’exécution est terminée et le mot est refusé.
Les différents types d’automates
Ce que nous avons décrit ici, c’est un automate à état fini déterministe (deterministic finite automaton, en anglais). Un automate à état fini, ou plus simplement automate fini, qu’on abrégera AF, est un type spécifique d’automate dont le nombre d’états est fini. Dans cette série d’articles nous intéresserons uniquement à ce type d’automate mais sachez qu’il en existe d’autres. L’image suivante (Wikipédia) montre les différentes classes d’automates :
Une machine de Turing est supposée capable de calculer tout ce qui est calculable et nos ordinateurs peuvent être ramenés à une machine de Turing. Je ferais peut-être une série d’articles sur les machines de Turing, mais ce n’est pas le propos ici.
Les automates finis sont plus limités et il y a un certain nombre de calculs qu’ils ne sont pas capables de faire. Cependant, il s’agit d’un objet plus simple à étudier.
Ici, nous nous intéressons plus particulièrement aux automates finis déterministes. Il s’agit du cas le plus simple des automates finis où il n’existe qu’une transition pour un état et un symbole donné et donc qu’une seule exécution possible pour un mot donné.
Les automates finis non-deterministes (AFND) et les automates finis non-deterministes avec ε-transitions (ε-AFND) seront étudiés par la suite. Tout AFND et ε-AFND pouvant être transformé en AFD, les algorithmes que nous étudierons pour les AFD resteront applicables.
Il existe aussi les automates finis non-ambiguës qui ne seront pas abordés ici.
Encore des définitions
Ça fait pas mal de définitions je sais, mais on approche de la fin.
Un mot w ∈ Σ*, est donc une séquence de symboleq de l’alphabet. Le mot vide est noté ε.
On appellera configuration, un couple (q, w), avec q ∈ Q et w ∈ Σ*. Une configuration est donc une paire d’un état et d’un mot, qui représente un stade particulier de l’exécution d’un automate.
Pour reprendre l’automate d’exemple, l’exécution pour le mot bbab donne lieu à la série de configurations suivante :
- (0, bbab) : configuration initiale.
- (0, bab).
- (0, ab).
- (1, b).
- (1, ε).
Une exécution pour un mot w est donc une séquence de configurations ayant pour configuration initiale (q0, w).
L’ensemble des mots de Σ qui sont acceptés par un automate A est appelé langage reconnu, noté L(A). On appelle langage à états, un langage pour lequel il existe un automate fini qui le reconnait.
Représentation d’un automate
Il existe différentes façons de représenter un automate.
Nous avons déjà vu la représentation graphique de l’automate d’exemple. On peut également le définir à l’aide du quintuplet (Q, qinit, Σ, δ, F), qui donne : ({0, 1}, 0, {a, b}, {(0, a, 1), (0, b, 0), (1, a, 1), (1, b, 1)}, {1}).
D’autres représentations existent, notamment la représentation à l’aide d’un tableau :
| Etat / Symbole | a | b |
|---|---|---|
| 0 (initial) | 1 | 0 |
| 1 (final) | 1 | 1 |
Ici, j’ai choisi d’indiquer à côté de chaque état s’il est initial ou accepteur. Vous croiserez surement beaucoup de variantes de cette représentation, de la même manière qu’il existe des variantes de la représentation graphique. L’important étant de clairement définir la notation.
A quoi servent les automates ?
La théorie des automates est une branche de l’informatique théorique. Ils sont utilisés dans les domaines de la calculabilité et la complexité, la preuve formelle et la vérification de modèle (avec Coq par exemple), la théorie des langages et les compilateurs ou encore les circuits logiques.
Les automates finis consistent une sous-partie intéressante puisqu’ils reconnaissent ce qu’on appelle les langages réguliers (ou encore langages rationnels ou langages à états) qui sont les langages reconnus par les expression régulières. Les expressions régulières, extrêmement utiles en informatique pour le traitement de chaînes de caractères, sont d’ailleurs souvent abordées après l’études des AFD dans les cours d’informatique.
Les automates finis sont aussi très utiles lorsqu’il s’agit d’écrire des compilateurs, et plus particulièrement l’analyse lexicale, qui est souvent réduite à un ensemble d’automates finis. Par exemple, l’automate suivant reconnait quelques mots clefs du langage C :
Les automates sont donc un sujet très souvent étudié dans les formations en informatique. D’autant qu’ils permettent d’aborder la théorie des graphes, des structures de données fondamentales en informatique, puisqu’ils sont basiquement des graphes orientés.
Quelques exemples
Avant de terminer cet article, je vous propose une petite série d’exemples d’AFD qui vous permettront de mieux saisir le principe. N’hésitez pas à chercher les solutions par vous-même et à faire des exécutions avec des mots simples pour vérifier vos automates.
Pour dessiner les automates, j’ai utilisé AUtomata DEmystifier (AUDE), qui est un outil permettant de dessiner, de manipuler et d’exécuter des automates. Ce projet initié en 2012 est le fruit du travail de plusieurs étudiants de l’Université de Grenoble-Alpes (UGA), il est disponible en version web et en version bureau. Il offre l’implémentation des algorithmes liés aux automates et permet même de visualiser une exécution pas à pas, ce qui en fait un très bonne outil pour apprendre et enseigner les automates, ainsi que pour en dessiner simplement. Je vous conseille donc fortement d’aller y jeter un œil.
Exemple 1 : un automate reconnaissant les mots avec un nombre pair de 0 sur l’alphabet Σ = {0, 1} :
Cet exemple est assez simple et ne nécessite que deux états : un lors que le nombre de 0 est pair et l’autre lorsque le nombre de 0 est impair. Les transitions avec le symbole 1 ne changent pas l’état courant.
Exemple 2 : un automate reconnaissant les entiers binaires pairs :
La première chose à faire est de se rendre compte qu’un entier en binaire est multiple de deux si et seulement si son bit de poids faible vaut 0.
Ici, on a un petit problème d’énoncé. L’automate est très différent selon qu’on prenne le mot avec le bit de poids fort en premier (MSB) ou le bit de poids faible en premier (LSB).
Avec le bit de poids faible en premier, c’est très facile, il nous suffit d’accepter les mots dont le premier symbole est 0.
Avec le bit de poids fort en premier (ce qui est la façon classique de traiter le nombre puisqu’on lit le mot de gauche à droite), l’automate est légèrement plus complexe :
Exemple 3 : un automate reconnaissant les mots contenant la séquence aaba sur l’alphabet Σ = {a, b} :
Cet exemple est un poil plus complexe mais est en fait assez simple. Il s’agit ici de reconnaître une séquence de symboles.
Lorsque vous devez construire un automate de cette sorte, commencez par créer les transitions lorsque la séquence est la bonne :
Une fois cette première étape réussie, il nous suffit de compléter les transitions manquantes en se posant la question suivante : “à ce stade, si je récupère tel symbole, où est-ce que j’en suis dans ma séquence” :
- Pour l’état 0 le symbole manquant est b : si on obtient un b, il faut revenir au début.
- Pour l’état 1, de la même manière on revient au début.
- Pour l’état 2, le symbole est a. On se rends compte ici que si on obtient un a après avoir reconnu aa, on reconnait donc la séquence aaa. Puisqu’une partie de la séquence à reconnaître est préservée, il faut que la transition aille sur l’état correspondant, à savoir l’état 2.
- Pour l’état 3 il faut encore une fois revenir au début si un b est trouvé.
Une bonne solution peut aussi de renommer les états en fonction de la séquence déjà obtenue pour faciliter l’écriture de l’automate. Ici, les états 0, 1, 2, 3 et 4 deviendraient les états ε, a, aa, aab et aaba.
Exemple 4 : un automate reconnaissant les mots contenant autant de a que de b (|a| = |b|) sur l’alphabet Σ = {a, b} :
Difficile n’est-ce pas ? En fait, c’est même impossible.
Le langage considéré n’est tout simplement pas un langage à états. Je ne vais pas vous présenter la démonstration mathématique (le lemme d’itération marcherait ici), mais voici un petit exemple pour comprendre pourquoi.
La méthode la plus évidente serait de nommer nos états en fonction du rapport de a et de b dans le mot. Au départ, on a autant de a que de b, l’état initial 0 est accepteur. Si on rencontre un a, on va dans l’état +1a qui correspond au cas où il y a un |a| = |b| + 1. Si on rencontre un b, on va dans l’état +1b, où |b| = |a| + 1.
Dans l’état +1a, si on rencontre un b, on retourne à l’état initial. Mais si on a un nouveau un a, il va falloir rejoindre l’état +2a :
En fait, pour être capable de compter la différence entre le nombre de a et le nombre de b, il va nous falloir un nombre infini d’états puisque cette différence est potentiellement infinie (tant que la taille d’un mot n’est pas bornée).
Il s’agit là d’un bon exemple de cas où un langage n’est pas reconnaissable par un AFD.
Voilà donc pour aujourd’hui ! Nous avons vu les fondamentaux concernant les automates et plus particulièrement les AFD.
Dans le prochain article, nous nous intéresserons à créer les bases de notre implémentation d’automate fini déterministe en Python. Cette implémentation servira de support pour le reste de la série d’articles.
En attendant, je vous remercie de m’avoir lu et je vous dis à bientôt !
You must log in to post a comment.