Construction d'un AFD simple.

Bonjour,

Dans la leçon précédente, nous avons établi les fondations de notre étude en définissant formellement un automate fini déterministe (AFD) et en apprenant à simuler son exécution sur une chaîne d'entrée. Vous savez maintenant qu'un AFD est un quintuplet $A = (Q, Σ, δ, q_{0}, F)$ et comment il accepte ou rejette un mot.

Aujourd'hui, nous passons de l'analyse à la synthèse, un exercice intellectuel fondamental pour l'Agrégation. L'objectif n'est plus de comprendre un automate existant, mais de construire vous-même un AFD pour un langage régulier simple décrit en français. Cette leçon vous dotera d'une méthodologie systématique pour traduire une description de langage en une machine formelle qui le reconnaît.

1. La Méthodologie de Construction d'un AFD

Construire un AFD n'est pas un processus aléatoire ; cela suit une démarche logique rigoureuse. La clé est de comprendre que les états de l'automate représentent sa mémoire. Puisque cette mémoire est finie (le nombre d'états est fini), nous devons identifier l'information essentielle et limitée que la machine doit retenir sur le préfixe de la chaîne lue jusqu'à présent pour décider de l'avenir.

Voici la démarche que je vous propose de suivre :

Identifier l'alphabet ( $Σ$ ) : Quels sont les symboles autorisés dans les mots du langage ?
Définir la sémantique des états : C'est l'étape la plus importante. Pour chaque état que vous créez, vous devez pouvoir répondre précisément à la question : "Dans quel cas la machine se trouve-t-elle dans cet état ?". Chaque état doit correspondre à une propriété spécifique du préfixe déjà lu (par exemple, "le préfixe se termine par 'a'", "le préfixe contient un nombre pair de 'b'", etc.).
Définir l'état initial ( $q_{0}$ ) : Cet état correspond toujours à la lecture du mot vide, $ϵ$ . Il représente l'information que nous avons avant de commencer à lire la chaîne.
Définir le ou les états accepteurs ( $F$ ) : Parmi les états que vous avez définis, lesquels correspondent à des préfixes qui sont des mots complets et valides du langage ?
Construire la fonction de transition ( $δ$ ) : Pour chaque état et chaque symbole de l'alphabet, déterminez l'état suivant. Posez-vous la question : "Si je suis dans un état qui a la sémantique S et que je lis le symbole x, quelle est la nouvelle sémantique du préfixe augmenté, et donc, dans quel état dois-je passer ?".
Assurer la complétude (et l'état puits) : Un AFD doit avoir une transition définie pour chaque couple (état, symbole). Si, à un moment donné, la chaîne lue ne pourra plus jamais appartenir au langage, on la dirige vers un état puits (ou "trap state"), un état non-accepteur dont toutes les transitions bouclent sur lui-même.

Appliquons immédiatement cette méthode.

2. Exemple 1 : Langages définis par leur préfixe

Considérons un problème classique : construire un AFD qui accepte toutes les chaînes sur l'alphabet $Σ = {0, 1}$ qui commencent par '0'.

La vidéo suivante illustre parfaitement la construction pas à pas de cet automate.

Deterministic Finite Automata (Example 1)

Cette vidéo de Neso Academy, intitulée 'Deterministic Finite Automata (Example 1)', détaille la conception d'un AFD pour le langage des chaînes qui commencent par '0'. Suivez attentivement le raisonnement pour chaque décision.

Regardez la vidéo de 00:24 à 06:05. Concentrez-vous sur la manière dont les trois états sont introduits et leur rôle : L'état initial. L'état final (accepteur), atteint dès que la condition 'commence par 0' est remplie. L'état 'mort' ou 'puits' (dead/trap state), atteint si la chaîne commence par '1'.

Analysons cette construction avec notre méthodologie :

Alphabet $Σ$ : ${0, 1}$ .
Sémantique des états :
- État A ( $q_{0}$ , initial) : On n'a encore rien lu.
- État B ( $q_{f}$ , accepteur) : Le préfixe lu a commencé par un '0'.
- État C ( $q_{p}$ , puits) : Le préfixe lu a commencé par un '1'.
État initial : A, car le mot vide $ϵ$ n'a pas encore commencé par '0' ou '1'.
État accepteur : B, car toute chaîne commençant par '0' doit être acceptée, quelle que soit la suite.
Transitions $δ$ :
- Depuis A : si on lit '0', on passe en B (la condition est remplie). Si on lit '1', on passe en C (la condition est échouée à jamais).
- Depuis B : si on lit '0' ou '1', on reste en B. La chaîne a déjà commencé par '0', elle reste acceptée.
- Depuis C : si on lit '0' ou '1', on reste en C. La chaîne a déjà échoué, elle restera rejetée.

La vidéo continue en validant l'automate sur les chaînes '001' (acceptée) et '101' (rejetée) entre 06:05 et 09:16. Je vous encourage à faire ce traçage mentalement pour vous assurer de votre compréhension.

3. Exemple 2 : Langages définis par une sous-chaîne

Complexifions légèrement. Construisons un AFD qui accepte le langage sur $Σ = {0, 1}$ des mots contenant la sous-chaîne '00'.

Quelle information devons-nous mémoriser ici ?

Nous n'avons pas encore vu de '0' pertinent.
Nous venons de voir un '0', donc le prochain caractère pourrait être un second '0'.
Nous avons déjà vu la sous-chaîne '00'.

Cela nous suggère trois états. La vidéo suivante construit un automate pour un problème analogue (détecter '11').

Regular Languages: Deterministic Finite Automaton (DFA)

Cette vidéo de la chaîne 'lydia' construit un AFD pour détecter une 'heatwave', définie comme deux jours consécutifs avec une température élevée. En remplaçant 'température élevée' par '1', c'est l'automate pour le langage des chaînes contenant '11'.

Regardez la vidéo de 01:01 à 03:17. Observez comment les états q0, q1, et q2 correspondent précisément aux trois niveaux d'information que nous avons identifiés : 'rien vu', 'vu un 1', 'vu 11'.

Maintenant, adaptez ce que vous venez de voir pour notre problème (contenir '00') :

Sémantique des états :
- $q_{0}$ (initial) : Le préfixe lu ne se termine pas par '0'.
- $q_{1}$ : Le préfixe lu se termine par un seul '0'.
- $q_{2}$ (accepteur) : Le préfixe lu contient la sous-chaîne '00'.
Transitions $δ$ :
- Depuis $q_{0}$ : si on lit '1', on reste en $q_{0}$ . Si on lit '0', on passe en $q_{1}$ .
- Depuis $q_{1}$ : si on lit '1', le '0' que l'on avait vu est "perdu", on retourne en $q_{0}$ . Si on lit '0', on passe en $q_{2}$ (succès !).
- Depuis $q_{2}$ : si on lit '0' ou '1', on reste en $q_{2}$ . Une fois la sous-chaîne trouvée, le mot est accepté définitivement.

Ce principe de "chaîne d'états" qui mémorise la progression vers la reconnaissance d'un motif est très courant. L'image suivante montre la solution pour un motif un peu plus long, "abc". La logique est la même.

Exercices sur les Automates Finis et Langages Réguliers — Cet AFD reconnaît toute chaîne contenant "abc". Observez les états qui mémorisent successivement "je n'ai rien vu", "je viens de voir 'a'", "je viens de voir 'ab'", et enfin l'état accepteur "j'ai vu 'abc'".

4. Synthèse et Formalisation

La construction d'un AFD consiste à matérialiser une "mémoire" sous forme d'états et de transitions. Une fois le diagramme esquissé, il est crucial de pouvoir le formaliser avec le quintuplet $A = (Q, Σ, δ, q_{0}, F)$ , comme vu dans la leçon précédente.

Le document de référence ci-dessous fournit une définition formelle rigoureuse ainsi qu'un autre exemple classique : l'automate reconnaissant le langage $L = {a^{n} b^{p} ∣ n > 0, p > 0}$ .

[PDF] Théorie des langages - CNRS

Le document 'Théorie des langages' du CNRS formalise la notion d'AFD et de son exécution. Il est important de vous familiariser avec ce niveau de formalisme.

Consultez la section 3.3 'Automates Finis Déterministes' (page 17). Relisez la définition formelle d'un AFD et analysez l'exemple graphique donné. Essayez de comprendre pourquoi l'état U est l'état final et comment l'état E sert d'état puits.

Exercice de Réflexion

Pour aller plus loin, considérons un type de langage différent, où la propriété à mémoriser n'est pas un motif, mais une propriété arithmétique.

DFA Design Example: Sum of Symbols Multiple of 3 — Cet AFD, sur l'alphabet $\{0, 1, 2\}$, accepte les mots dont la somme des chiffres est un multiple de 3. Par exemple, "12" est accepté (1+2=3), "11" est rejeté (1+1=2).

Question pour vous : en appliquant notre méthodologie, quelle est la sémantique de chacun des trois états $a_{0}, a_{1}, a_{2}$ ? Autrement dit, quelle information sur le préfixe lu l'automate doit-il mémoriser pour prendre sa décision ?

Cliquez ici pour la réponse

L'information cruciale à mémoriser est le reste de la division par 3 de la somme des chiffres du préfixe lu.

État $a_0$ : La somme des chiffres lus est congrue à 0 modulo 3. C'est l'état initial (somme de $\epsilon$ = 0) et l'état final.
État $a_1$ : La somme des chiffres lus est congrue à 1 modulo 3.
État $a_2$ : La somme des chiffres lus est congrue à 2 modulo 3.

Par exemple, si l'on est dans l'état $a_1$ (somme $\equiv 1 \pmod 3$) et que l'on lit '2', la nouvelle somme est $\equiv 1+2 \equiv 3 \equiv 0 \pmod 3$. On passe donc à l'état $a_0$.

Conclusion

Aujourd'hui, vous avez acquis une compétence essentielle : la capacité de transformer une description abstraite de langage en un modèle de calcul concret et formel.

Points clés à retenir :

La construction d'un AFD est une démarche systématique basée sur l'identification de la mémoire finie nécessaire.
La sémantique des états est le cœur de la conception : chaque état encode une propriété du préfixe lu.
La construction des transitions consiste à mettre à jour cette propriété à la lecture de chaque nouveau symbole.
L'état puits est un outil indispensable pour gérer les échecs irrécupérables et garantir la complétude de l'automate.

Dans notre prochaine leçon, nous introduirons le concept d'automate fini non déterministe (AFN). Vous verrez que pour certains langages, les AFN sont plus simples et plus intuitifs à construire. Nous prouverons ensuite un résultat fondamental : malgré cette simplicité, les AFN ne sont pas plus puissants que les AFD.

Recommended resources