#AFN et AFDCopier le lien

Les automates finis sont des machines abstraites qui reconnaissent exactement les langages rationnels, ceux décrits par les expressions régulières. Un automate lit un mot symbole par symbole et répond oui ou non. Deux variantes coexistent: l'automate fini déterministe (AFD), où chaque symbole lu mène à un état unique, et l'automate fini non déterministe (AFN), où plusieurs exécutions se déroulent en parallèle. Déterminiser un AFN et minimiser un AFD sont les deux opérations centrales de ce chapitre.

Prérequis: alphabets et mots (concaténation, mot vide ε), notion de langage comme ensemble de mots, bases des expressions régulières (page Regex de ce module), manipulation d'ensembles (union, inclusion, complémentaire) utilisée par la construction par sous-ensembles.

Objectifs d'apprentissage:

• Écrire formellement un automate (états, alphabet, transitions, initial, acceptants) et exécuter sa sémantique sur un mot.
• Distinguer AFD, AFN et AFN à ε-transitions, et lire le langage accepté par un automate.
• Déterminiser un AFN par la construction par sous-ensembles (avec ε-fermeture) sur un exemple complet.
• Minimiser un AFD par raffinement de partitions et citer la complexité de chaque opération.

#Définition formelleCopier le lien

Un automate fini est un quintuplet A = (Q, Σ, δ, q0, F):

• Q: ensemble fini d'états.
• Σ: alphabet, ensemble fini de symboles.
• δ: fonction de transition, dont la forme dépend du modèle.
• q0 ∈ Q: état initial. Un seul, même pour un AFN.
• F ⊆ Q: ensemble des états acceptants.

La différence AFD/AFN ne porte que sur δ:

• AFD: δ : Q × Σ → Q. Pour chaque état et chaque symbole, exactement une transition. Une seule exécution possible par mot.
• AFN: δ : Q × Σ → P(Q). Zéro, une ou plusieurs transitions par couple (état, symbole).
• AFN avec ε-transitions: on autorise en plus des transitions étiquetées ε, franchissables sans consommer de symbole. C'est le format produit par la construction de Thompson.

#Sémantique: le langage acceptéCopier le lien

Un mot w est accepté par un AFN s'il existe au moins un chemin de q0 vers un état de F dont l'étiquette est w (les ε-transitions se traversent gratuitement). Le langage L(A) est l'ensemble des mots acceptés. Un AFD incomplet qui se bloque rejette le mot; en pratique on le complète avec un état mort, qui boucle sur lui-même et n'est jamais acceptant.

Trois points souvent mal compris:

• Le non-déterminisme n'ajoute aucune puissance d'expression: AFN et AFD reconnaissent exactement les mêmes langages. Il ne fait que compacter la description, parfois massivement: un AFN à n états peut demander jusqu'à 2^n états une fois déterminisé.
• Un état acceptant n'arrête pas la lecture. L'automate consomme tout le mot, puis on regarde où il atterrit. Seul le dernier état compte.
• Le mot vide ε est accepté si et seulement si q0 ∈ F. C'est le premier test à faire quand on vérifie un automate.

#Panorama: de la regex à l'AFD minimalCopier le lien

#Simulateur AFDCopier le lien

Un AFD s'exécute en un seul passage sur le mot, en temps linéaire, sans retour arrière.

Vérification rapide: 01, 101, 1101, 0101 finissent par 01 et sont acceptés; 10 et 111 sont rejetés; le mot vide '' est rejeté car A n'est pas acceptant. Notez que chaque état encode une information sur le suffixe déjà lu: c'est l'intuition à garder pour construire un AFD directement.

#Déterminisation: la construction par sous-ensemblesCopier le lien

L'idée: simuler toutes les exécutions parallèles de l'AFN en même temps. Un état du nouvel AFD est un ensemble S ⊆ Q d'états de l'AFN, à lire comme « les états où l'AFN pourrait être après avoir lu ce préfixe ». Formellement:

• État initial de l'AFD: ε-fermeture({q0}).
• Transition: δ'(S, a) = ε-fermeture( ∪ δ(q, a) pour q ∈ S ).
• L'état-ensemble S est acceptant si S ∩ F ≠ ∅.

L'ε-fermeture d'un ensemble S est S plus tous les états atteignables depuis S en ne suivant que des ε-transitions. Elle se calcule par un parcours en profondeur tout bête.

#Exemple complet: AFN de (a|b)*abCopier le lien

Construisons un AFN pour L = (a|b)*ab, l'ensemble des mots sur {a, b} qui finissent par ab. Q = {q0, q1, q2}, initial q0, acceptants {q2}:

• q0 --a,b--> q0: boucle qui réalise (a|b)*
• q0 --a--> q1: l'AFN devine que le suffixe final ab commence ici
• q1 --b--> q2: le mot se termine juste après ce ab

Déterminisons pas à pas. Pas d'ε-transitions ici, donc l'état initial de l'AFD est {q0}:

1. S0 = {q0}. Sur a: δ(q0,a) = {q0, q1}, nouvel état S1. Sur b: {q0} = S0.
2. S1 = {q0, q1}. Sur a: {q0, q1} = S1. Sur b: {q0} ∪ {q2} = {q0, q2}, nouvel état S2.
3. S2 = {q0, q2}. Sur a: {q0, q1} = S1. Sur b: {q0} = S0.

Trois états suffisent. S2 est le seul acceptant car q2 ∈ S2. On retrouve la mécanique du simulateur précédent: S0, S1, S2 correspondent aux trois situations « rien d'utile », « dernier symbole a », « suffixe ab lu ». L'AFD obtenu est déjà minimal: les trois états sont deux à deux distinguables, S0 et S1 par le suffixe b, S0 et S2 par le mot vide.

#Le même calcul en PythonCopier le lien

Sorties attendues: trois états {q0}, {q0,q1}, {q0,q2}; seul {q0,q2} est acceptant; ab, aab, abab sont acceptés, le mot vide, ba et abb rejetés. Si votre exécution diverge, vérifiez en priorité l'ε-fermeture et l'union des transitions depuis chaque état de S.

#Minimisation d'un AFD par raffinementCopier le lien

Deux états d'un AFD sont équivalents si tout suffixe est accepté depuis l'un exactement quand il l'est depuis l'autre. La minimisation fusionne chaque classe d'équivalence en un seul état. Algorithme de Moore, par raffinement de partitions:

1. Émonder: supprimer les états inaccessibles depuis q0, et compléter avec un état mort si nécessaire.
2. Partition initiale: acceptants F contre non acceptants Q − F.
3. Raffiner: dans chaque bloc, séparer les états dont les transitions, pour un même symbole, mènent à des blocs différents. Répéter jusqu'à stabilisation.
4. Reconstruire: chaque bloc devient un état; les transitions se lisent sur n'importe quel représentant du bloc.

Résultat remarquable: l'AFD minimal d'un langage est unique à un renommage des états près. Conséquence pratique: deux AFD reconnaissent le même langage si et seulement si leurs minimisés sont isomorphes. C'est un test d'égalité de langages bien plus fiable que de tâtonner sur des exemples.

Lecture du résultat: trois blocs {A,C,E}, {B}, {D}. Les transitions reconstruites sont exactement celles du simulateur du début de page: {A,C,E} joue le rôle de A, {B} celui de B, {D} celui de C. Les cinq états de départ décrivaient le même langage avec deux états superflus. Pour vérifier votre propre exécution, faites tourner une dizaine de mots sur l'AFD initial puis sur l'AFD minimal: les verdicts doivent coïncider à chaque fois.

#Construire un AFD directement depuis un cahier des chargesCopier le lien

Le réflexe qui fait gagner du temps en examen: quand un langage est décrit par des règles en français, il faut identifier ce que l'automate doit « savoir » du préfixe déjà lu, puis nommer un état par chacune de ces situations. L'exercice 1 des annales de ce module en donne un exemple complet, sur l'alphabet $\{a,m\}$:

• a peut être suivi par $\varepsilon$, m ou mm, mais pas par a;
• m peut être suivi par $\varepsilon$, a ou m, sans jamais trois m consécutifs;
• mm doit être suivi par a;
• un mot ne peut ni commencer ni terminer par mm.

Ce que l'automate doit retenir du préfixe, c'est uniquement son dernier symbole, et s'il s'agit d'un m, depuis combien de temps. Six situations suffisent:

Lecture des transitions: depuis $q_a$, lire a produirait aa, interdit (mort); lire m produit am$. Depuis $q_{am}$, lire mproduitamm($q_{amm}$), et depuis $q_{amm}$ liremproduiraitmmm(mort) alors que lireaproduitamma, qui se termine par a($q_a$). Depuis $q_m$, liremproduirait un mot **commençant** parmm, interdit (mort); lire aproduitma`.

Trois vérifications sur ce tableau:

• $q_{amm}$ est non acceptant: un mot terminé par mm est interdit, même si tout le reste est correct. C'est le seul état non acceptant hors l'état mort, et c'est exactement la règle « un mot ne peut pas terminer par mm ».
• $q_0$ et $q_m$ sont acceptants: le mot vide et le mot m appartiennent au langage, et l'énoncé le confirme en citant mam comme valide.
• L'état mort n'est pas un oubli: dès qu'une infraction est commise, aucun suffixe ne peut la réparer (les règles portent sur des facteurs du mot, qui restent présents). Le langage est donc préfixe-fermé par rejet définitif, ce qui justifie l'état puits.

Les six états sont deux à deux distinguables, donc cet AFD est minimal. La leçon générale: le nombre d'états est dicté par le nombre de situations distinctes du préfixe, pas par la longueur de l'énoncé en français. Un cahier des charges de quatre règles tient ici en six états, alors que la construction par sous-ensembles depuis l'expression régulière $m?\,(am+amm)^*(a+am) + \varepsilon + m$ en produirait davantage avant minimisation.

#Opérations sur les langages et clôtureCopier le lien

Les langages rationnels sont clos par union, intersection, complémentaire, concaténation, étoile, miroir et morphisme. Les trois premières se démontrent sur les automates, ce qui est la façon la plus économique de s'en souvenir.

Complémentaire. Il ne suffit pas d'échanger états acceptants et non acceptants: encore faut-il que l'automate soit complet et déterministe. Sinon un mot rejeté parce qu'aucune transition n'existe ne serait pas accepté par l'automate modifié. La recette complète est donc:

1. déterminiser l'AFN;
2. compléter avec un état mort si des transitions manquent;
3. échanger $F$ et $Q \setminus F$.

Le point 2 est celui qu'on oublie. Sur l'automate à trois états de $(a|b)^*ab$, la transition depuis $q_0$ sur b existe (elle boucle), mais un automate incomplet rejetterait un mot simplement en se bloquant; après échange des états acceptants, ce mot se retrouverait accepté, ce qui est faux.

Intersection. On construit le produit synchronisé des deux AFD: les états sont les couples $(p, q)$, l'état initial est $(p_0, q_0)$, et $\delta((p,q), a) = (\delta_1(p,a), \delta_2(q,a))$ Un couple est acceptant si les deux composantes le sont. La preuve tient en une ligne: l'automate produit simule les deux automates en parallèle, donc il accepte $w$ si et seulement si les deux l'acceptent. La taille est $|Q_1| \times |Q_2|$.

Union. Même construction, avec un état acceptant si l'une des composantes l'est. (Ou, plus simplement, par les automates non déterministes: un nouvel état initial avec deux $\varepsilon$-transitions.) On peut aussi écrire $L_1 \cup L_2 = \overline{\overline{L_1} \cap \overline{L_2}}$ et réutiliser les deux opérations précédentes.

Différence. $L_1 \setminus L_2 = L_1 \cap \overline{L_2}$: conséquence immédiate des deux précédentes.

Ce que la clôture ne donne pas: la classe n'est pas close par intersection infinie. L'intersection des langages $\{a^n b^m : m \le n\}$ pour $n \in \mathbb{N}$ vaut $\{a^n b^n : n \in \mathbb{N}\}$, qui n'est pas rationnel, alors que chacun des termes de l'intersection l'est. Un nombre fini d'opérations préserve la rationalité; une infinité non.

#La borne $2^n$ est atteinteCopier le lien

Un AFN à $n$ états peut exiger $2^n$ états une fois déterminisé — et cette borne est atteinte, pas seulement majorante. Le témoin canonique est

$L_n = \{\,w \in \{0,1\}^* : \text{le } n\text{-ième symbole en partant de la fin est un } 1\,\}$

Cet ensemble est reconnu par un AFN à $n+1$ états: on devine, au moment de lire un 1, qu'il est le $n$-ième depuis la fin, puis on compte $n-1$ symboles supplémentaires avant d'accepter. En revanche, tout AFD le reconnaissant doit avoir au moins $2^n$ états: après avoir lu un préfixe, la seule information utile est les $n-1$ derniers symboles, et deux préfixes ayant des $n-1$ derniers symboles différents se distinguent par un suffixe convenablement choisi. Or il y a $2^{n-1}$ suites de $n-1$ symboles, et il faut en plus mémoriser le symbole courant, d'où $2^n$ classes. Vérification pour les petites valeurs: $n = 1$ donne 2 états, $n = 2$ en donne 4, $n = 3$ en donne 8 — exactement $2^n$ dans les trois cas.

Conséquence pratique: la déterminisation peut être exponentielle, et c'est un mur, pas un défaut d'implémentation. En contrepartie, une fois l'AFD obtenu, l'exécution est en $O(|w|)$ avec une table indexée par (état, symbole), sans retour arrière.

#Reconnaître un langage: AFN, AFD, AFD minimalCopier le lien

Résumons la chaîne complète, avec la garantie associée à chaque étape:

L'unicité de l'AFD minimal est l'outil théorique le plus utile de ce chapitre: elle transforme la question « ces deux automates reconnaissent-ils le même langage? » en « leurs minimisés sont-ils isomorphes? », qui est décidable et se calcule. Deux langages sont égaux si et seulement si leurs AFD minimaux sont identiques à renommage des états près. Sur le plan pratique, c'est aussi ce qui permet de vérifier qu'une optimisation d'automate (factorisation, fusion d'états) n'a pas changé le langage reconnu.

#Le lemme de l'étoile: prouver qu'un langage n'est pas rationnelCopier le lien

Savoir construire un AFD ne dit pas comment prouver qu'il n'en existe pas. L'outil est le lemme de l'étoile (pumping lemma), et c'est la question la plus rentable des sujets d'examen: elle demande une rédaction rigoureuse, pas un calcul.

#ÉnoncéCopier le lien

Si $L$ est un langage rationnel, alors il existe un entier $p \ge 1$ (la longueur de pompage) tel que tout mot $w \in L$ de longueur $|w| \ge p$ se décompose en

$w = xyz \quad\text{avec}\quad |xy| \le p, \quad |y| \ge 1, \quad\text{et}\quad \forall i \ge 0,\ xy^{i}z \in L$

Pourquoi c'est vrai. Si $L$ est rationnel, il est reconnu par un AFD à $p$ états. Un mot de longueur $\ge p$ traverse au moins $p+1$ états, donc deux fois le même état (principe des tiroirs). Soit $y$ le facteur lu entre ces deux visites: il forme une boucle dans l'automate. On peut donc la parcourir zéro fois, une fois, ou $i$ fois, et le mot reste accepté. Les bornes $|xy| \le p$ et $|y| \ge 1$ viennent du choix de la première répétition, qui survient avant d'avoir lu $p$ symboles.

#Schéma de preuve par l'absurdeCopier le lien

1. Supposer $L$ rationnel, de longueur de pompage $p$.
2. Choisir un mot témoin $w \in L$ de longueur $\ge p$, dont la structure est « rigide ».
3. Le lemme donne $w = xyz$ avec $|xy| \le p$ et $|y| \ge 1$: ces bornes restreignent $y$, c'est là que réside toute la force de l'argument.
4. Pomper (souvent $i = 0$ ou $i = 2$) et montrer que $xy^{i}z \notin L$.
5. Contradiction: $L$ n'est pas rationnel.

#Exemple complet: $a^nb^n$ n'est pas rationnelCopier le lien

Soit $L = \{a^nb^n : n \ge 0\}$. Supposons $L$ rationnel, de longueur de pompage $p$, et prenons

$w = a^p\,b^p$

Ce mot appartient à $L$ et $|w| = 2p \ge p$. Par le lemme, $w = xyz$ avec $|xy| \le p$ et $|y| \ge 1$. Comme $|xy| \le p$ et que les $p$ premiers symboles de $w$ sont des a, le facteur $xy$ est entièrement composé de a; donc $y = a^{k}$ avec $1 \le k \le p$.

Pompons vers le haut ($i = 2$): $xy^2z = a^{p+k}b^{p}$. Ce mot contient $p+k$ symboles a et $p$ symboles b, avec $k \ge 1$, donc plus de a que de b: il n'appartient pas à $L$. Contradiction.

Rédaction attendue. Les trois points qui rapportent les points: la vérification de $|w| \ge p$; l'exploitation de $|xy| \le p$ pour localiser $y$ dans le bloc des a (c'est l'étape que les copies bâclées sautent); et le choix explicite de la valeur de $i$ avec le calcul de la longueur obtenue. Une preuve qui écrit « on pompe et ça ne marche plus » sans préciser ni où est $y$ ni combien vaut $i$ ne démontre rien.

#Un corollaire utile: le comptage non bornéCopier le lien

Le même argument s'applique à $L' = \{w \in \{a,b\}^* : \#_a(w) = \#_b(w)\}$, qui est le « langage des mots équilibrés ». La preuve directe est un peu plus délicate, mais on peut l'éviter par clôture: si $L'$ était rationnel, alors $L' \cap a^*b^*$ le serait aussi (la classe est close par intersection), or $L' \cap a^*b^* = \{a^nb^n : n \ge 0\} = L$, qui n'est pas rationnel. Contradiction. Cette technique — ramener un nouveau langage à un langage déjà connu non rationnel par intersection avec un langage rationnel bien choisi — est souvent plus courte que d'appliquer le pompage directement.

#Ce que le lemme ne dit pasCopier le lien

Attention au contresens: le lemme est une condition nécessaire, pas suffisante. Un langage non rationnel peut très bien satisfaire la conclusion du lemme. Par exemple, il existe des langages non rationnels $L$ pour lesquels tout mot suffisamment long se décompose et se pompe comme le lemme l'exige. Le lemme sert donc uniquement à démontrer la non-rationalité (par l'absurde); il ne permet jamais de conclure qu'un langage est rationnel. Pour prouver qu'un langage est rationnel, on exhibe un AFD, un AFN, une expression régulière, ou une combinaison close de langages rationnels connus.

#La version algébriqueCopier le lien

Pour les langages hors contexte, il existe un lemme analogue, dit lemme de l'étoile pour les langages algébriques: il existe $p \ge 1$ tel que tout $w \in L$ de longueur $\ge p$ s'écrive $w = uvxyz$ avec

$|vxy| \le p, \qquad |vy| \ge 1, \qquad uv^{i}xy^{i}z \in L \ \ \forall i \ge 0$

La différence structurelle compte: on pompe deux facteurs ($v$ et $y$) simultanément, et la borne porte sur $vxy$ au lieu de $xy$. C'est ce qui permet de montrer qu'un langage comme $\{1^{3^i} : i \ge 0\}$ n'est pas algébrique, alors que l'argument rationnel n'y suffit pas.

#Pourquoi convertir, et limitesCopier le lien

• Exécution: un AFD s'exécute en O(|w|), avec une table de transitions et aucun retour arrière. C'est le format idéal pour un lexer ou un validateur appelé en boucle.
• Explosion d'états: la déterminisation peut produire jusqu'à 2^n états pour un AFN à n états, et certaines familles de langages atteignent cette borne. La minimisation ramène ensuite l'AFD à sa taille canonique.
• Complexités: exécution O(|w|); construction par sous-ensembles O(2^n) au pire, mais souvent proche de n × |Σ| sur des exemples réalistes; minimisation O(n log n) avec Hopcroft, O(n²) avec Moore.
• Choix d'ingénierie: les moteurs usuels (PCRE, module re de Python) simulent l'AFN par retour arrière pour offrir captures et références arrière, au prix d'un temps exponentiel au pire cas. Les moteurs DFA (RE2, regex de Rust) compilent vers des automates et garantissent un temps linéaire, en renonçant précisément à ces extensions.

#Mini-quizCopier le lien

#Exercice: déterminiser puis minimiserCopier le lien

Soit l'AFN sur l'alphabet {a, b} défini par Q = {0, 1, 2}, initial 0, acceptants {2}, sans ε-transition:

• 0 --a--> {0, 1}
• 0 --b--> {0}
• 1 --b--> {2}
• 2 --a--> {2}
• 2 --b--> {2}

Déterminez cet AFN par la construction par sous-ensembles, puis minimisez l'AFD obtenu.

#Correction guidéeCopier le lien

Déterminisation, en traitant chaque état-ensemble à la file:

1. {0}. Sur a: {0,1} (nouveau). Sur b: {0}.
2. {0,1}. Sur a: {0,1}. Sur b: {0} ∪ {2} = {0,2} (nouveau).
3. {0,2}. Sur a: {0,1} ∪ {2} = {0,1,2} (nouveau). Sur b: {0} ∪ {2} = {0,2}.
4. {0,1,2}. Sur a: {0,1} ∪ {2} = {0,1,2}. Sur b: {0,2}.

L'AFD a quatre états; {0,2} et {0,1,2} sont acceptants (ils contiennent 2). Le langage reconnu: les mots contenant ab quelque part.

Minimisation: partition initiale, bloc acceptant [{0,2}, {0,1,2}] contre bloc non acceptant [{0}, {0,1}]. Les signatures séparent {0} (sur b, reste dans le bloc non acceptant) de {0,1} (sur b, atteint le bloc acceptant). En revanche {0,2} et {0,1,2} ont le même comportement: sur a ils restent dans le bloc acceptant, sur b aussi. Ils fusionnent. Résultat: trois états, l'AFD minimal de « contient ab », avec ses trois situations: rien d'utile lu, un a en attente, ab déjà vu.

Méthode de vérification (à refaire systématiquement): listez les mots de longueur 0 à 3 acceptés et rejetés par l'AFN de départ, puis simulez les mêmes mots sur l'AFD déterminisé, puis sur l'AFD minimisé. Les trois listes doivent coïncider exactement. Une seule divergence localise une erreur de calcul, presque toujours une ε-fermeture oubliée ou une union de transitions incomplète.