Automates Finis Déterministes : Définition et Simulation

Bonjour,

Dans notre dernière leçon, nous avons conclu notre étude de la programmation dynamique en abordant la preuve de correction, une compétence essentielle pour valider la rigueur de vos algorithmes. Vous avez appris à structurer une preuve par récurrence sur la base des sous-problèmes, ce qui est un attendu fondamental à l'Agrégation.

Aujourd'hui, nous changeons de paradigme. Nous quittons le domaine de l'optimisation pour entrer dans celui de l'informatique théorique fondamentale : la théorie des automates. Ce domaine s'intéresse aux modèles de calcul et à leur pouvoir expressif. Nous commencerons par le modèle le plus simple, mais non moins puissant : l'Automate Fini Déterministe (AFD).

L'objectif de cette leçon est double : d'abord, comprendre la définition formelle et rigoureuse d'un AFD, puis apprendre à simuler son exécution sur une chaîne de caractères pour déterminer si celle-ci est "acceptée" ou "rejetée". C'est le premier pas indispensable pour comprendre les langages réguliers, les expressions régulières et les fondements de la compilation.

1. Introduction Intuitive : Une Machine à États Finis

Avant de nous plonger dans le formalisme mathématique, développons une intuition. Un automate fini est un modèle abstrait d'une machine qui lit une entrée, symbole par symbole, et décide à la fin si l'entrée est conforme à une règle prédéfinie. Son unique "mémoire" est l'état dans lequel elle se trouve à un instant donné.

Pour comprendre ce concept de modèle de calcul simple, je vous propose de visionner un court extrait d'une conférence de Michael Sipser, l'auteur de l'ouvrage de référence "Introduction to the Theory of Computation".

1. Introduction, Finite Automata, Regular Expressions

Cet extrait de la chaîne MIT OpenCourseWare introduit la notion d'automates finis comme des modèles de calculs abstraits avec une mémoire très limitée.

Regardez la vidéo de 09:23 à 10:49. L'idée principale à retenir est que nous utilisons des modèles simplifiés pour raisonner mathématiquement sur le calcul.

La manière la plus courante de représenter un automate est un diagramme d'états.

Diagramme de Transition d'un Automate Fini Déterministe (AFD) — Cette image illustre les conventions standards pour dessiner un automate : un cercle pour un état, une flèche "venant de nulle part" pour indiquer l'état initial, et un double cercle pour indiquer un état final (ou accepteur).

Regardons maintenant un exemple concret et comment il traite une entrée.

1. Introduction, Finite Automata, Regular Expressions

Continuons avec la vidéo du MIT. Le professeur Sipser présente un diagramme d'états et explique visuellement ses composantes.

Regardez de 10:49 à 11:54. Identifiez bien les trois types d'éléments : les états (q1, q2, q3), l'état initial (q1), l'état accepteur (q3) et les transitions (les flèches étiquetées par 0 ou 1).

Maintenant que nous avons les composants, voyons comment la machine "calcule". Elle part de l'état initial et, pour chaque symbole de la chaîne d'entrée, elle suit la flèche correspondante pour passer à un nouvel état. Si, après avoir lu toute la chaîne, la machine se trouve dans un état accepteur, la chaîne est acceptée ; sinon, elle est rejetée.

1. Introduction, Finite Automata, Regular Expressions

Cette dernière partie de l'extrait montre la simulation (ou l'exécution) de l'automate sur deux chaînes d'entrée différentes.

Regardez de 11:54 à 14:25. Suivez attentivement avec le pointeur le parcours des états pour l'entrée 01101 (qui est acceptée) et pour 00101 (qui est rejetée). C'est ce processus que nous appelons 'simuler l'exécution'.

2. Définition Formelle d'un Automate Fini Déterministe (AFD)

L'intuition visuelle est excellente, mais pour l'Agrégation, la rigueur mathématique est indispensable. Nous devons être capables de définir un AFD sans ambiguïté. Pour cela, nous utilisons un formalisme précis.

Je vous propose de lire les définitions dans le polycopié suivant, qui est une excellente ressource en français.

[PDF] IF114 – Automates finis et applications

Ce document de l'ENSEIRB-MATMECA, 'Automates finis et applications', fournit les définitions formelles que nous allons utiliser. Il distingue clairement les automates généraux des automates déterministes.

Lisez les sections 1.2 (jusqu'à la Définition 1.10) et concentrez-vous sur deux définitions clés : Définition 1.8 (Automate fini) : La définition générale. Définition 1.10 (Automate fini déterministe) : Les trois conditions qui rendent un automate déterministe. C'est le point crucial qui nous intéresse aujourd'hui.

En synthèse, un Automate Fini Déterministe (AFD) est un quintuplet (ou 5-uplet) $A = (Q, Σ, δ, q_{0}, F)$ où :

$Q$ est un ensemble fini d'états. (Les cercles dans notre diagramme).
$Σ$ est un ensemble fini de symboles, appelé l'alphabet. (Les étiquettes sur les flèches).
$δ : Q \times Σ \to Q$ est la fonction de transition. C'est le cœur du déterminisme : pour un état donné et un symbole donné, il y a un et un seul état de destination. C'est une fonction au sens mathématique.
$q_{0} \in Q$ est l'état initial. (L'état avec la flèche entrante).
$F \subseteq Q$ est l'ensemble des états accepteurs (ou finaux). (Les états en double cercle).

Pour bien voir le lien entre le diagramme et la fonction de transition $δ$ , on représente souvent cette dernière sous forme de tableau.

DFA State Diagram and Transition Table — Cette image montre un AFD sous ses deux formes : à gauche, le diagramme d'états visuel ; à droite, la table de transition qui représente la fonction $\delta$. Par exemple, on peut y lire que $\delta(0, 'a') = 1$ et $\delta(1, 'b') = 2$. C'est la même information, présentée différemment.

Pour renforcer cette définition formelle, écoutez à nouveau le professeur Sipser la présenter. La redondance entre des sources de qualité est une bonne stratégie d'apprentissage.

1. Introduction, Finite Automata, Regular Expressions

Retournons à la vidéo du MIT pour la définition formelle du 5-uplet.

Regardez de 18:33 à 22:07. Le professeur explique chaque composant du 5-uplet et justifie l'intérêt d'une définition formelle, notamment pour la précision et la description d'automates complexes.

3. Exécution Formelle et Langage Reconnu

Nous avons vu intuitivement comment un automate traite une chaîne. Formalisons maintenant ce processus en utilisant notre quintuplet.

Une exécution de l'AFD $A$ sur un mot $w = w_{1} w_{2} ... w_{n} \in Σ^{*}$ est une séquence d'états $r_{0}, r_{1}, ..., r_{n}$ telle que :

$r_{0} = q_{0}$ (la séquence commence à l'état initial).
Pour tout $i$ de 1 à $n$ , $r_{i} = δ (r_{i - 1}, w_{i})$ (chaque état successif est obtenu en appliquant la fonction de transition à l'état précédent et au symbole courant de l'entrée).

Le mot $w$ est accepté par $A$ si l'état final de l'exécution, $r_{n}$ , appartient à l'ensemble des états accepteurs $F$ . Sinon, $w$ est rejeté.

L'ensemble de tous les mots acceptés par $A$ est appelé le langage reconnu par $A$ , noté $L (A)$ .

[PDF] IF114 – Automates finis et applications

Le document de l'ENSEIRB-MATMECA formalise également ces notions avec une grande précision.

Lisez la section 1.2.1 'Langage accepté et langage reconnu'. Portez une attention particulière à la Définition 1.11 (Exécution) et à la Définition 1.13 (Langage reconnu). L'Exemple 1.9 illustre bien ce qu'est une exécution valide et invalide.

4. De la Théorie à la Pratique : Simulation en Python

Votre aisance en Python nous permet de rendre ces concepts très concrets. Comment représenter un AFD et simuler son exécution avec un programme ? La vidéo suivante, de la chaîne Computerphile, est excellente pour cela. Elle montre comment la définition formelle se traduit presque directement en une classe Python.

Automata & Python - Computerphile

Cette vidéo de Computerphile montre comment implémenter un AFD en Python pour reconnaître un langage simple : celui où toutes les lettres 'a' apparaissent avant toutes les lettres 'b'.

Regardez la vidéo de 0:00 à 09:10. Concentrez-vous sur les points suivants : (0:00 - 4:19) La construction du diagramme d'états pour le problème posé. (4:19 - 5:26) La simulation manuelle sur ce diagramme. (5:26 - 9:10) L'implémentation en Python. Observez comment le __init__ de la classe DFA stocke les 5 composants de notre tuple formel, et comment la méthode run implémente précisément le processus d'exécution que nous avons défini.

Cette implémentation est un excellent exemple de la manière dont la théorie des automates sert de fondement à des programmes très pratiques, comme les analyseurs lexicaux dans les compilateurs, qui sont chargés de reconnaître les "mots" du langage de programmation.

Conclusion

Aujourd'hui, vous avez franchi la première porte du monde de la théorie de la calculabilité. Vous avez appris à manipuler un concept fondamental, l'Automate Fini Déterministe, tant sur le plan intuitif et visuel que sur le plan formel et pratique.

Points clés à retenir :

Un AFD est un modèle de calcul simple pour la reconnaissance de motifs, caractérisé par une mémoire finie (ses états).
Il est défini formellement par un quintuplet $A = (Q, Σ, δ, q_{0}, F)$ .
La condition de déterminisme est cruciale : la fonction de transition $δ$ associe à chaque couple (état, symbole) un unique état de destination.
La simulation d'un AFD consiste à suivre séquentiellement les transitions à partir de l'état initial en lisant un mot d'entrée. Le mot est accepté si l'automate termine son parcours dans un état accepteur.
L'ensemble des mots acceptés par un automate forme le langage reconnu par cet automate.

Dans notre prochaine leçon, nous passerons de l'analyse à la synthèse. Au lieu de simuler un automate donné, vous apprendrez à construire vous-même un AFD pour reconnaître un langage simple décrit en français. C'est une compétence pratique fondamentale pour les épreuves de l'Agrégation.

Recommended resources

1. Introduction Intuitive : Une Machine à États Finis

2. Définition Formelle d'un Automate Fini Déterministe (AFD)

3. Exécution Formelle et Langage Reconnu

4. De la Théorie à la Pratique : Simulation en Python

Conclusion