AFD vers Expression Régulière : Algorithme de Kleene

Bonjour,

Dans notre leçon précédente, nous avons établi la première moitié de l'équivalence fondamentale entre les formalismes des langages réguliers, en montrant comment transformer une expression régulière en un automate fini non déterministe grâce à la construction de Thompson. Nous avons ainsi prouvé que tout langage descriptible par une expression régulière est reconnu par un automate.

Aujourd'hui, nous allons achever la démonstration du théorème de Kleene en abordant la direction inverse. L'objectif est de maîtriser une méthode algorithmique pour convertir un automate fini (AFD ou AFN) en une expression régulière équivalente. Cette construction, bien que plus complexe conceptuellement que celle de Thompson, est tout aussi fondamentale et constitue un attendu classique pour l'agrégation.

Nous étudierons la méthode la plus courante, souvent appelée algorithme de Kleene ou méthode d'élimination d'états. Elle repose sur une approche de programmation dynamique où l'on construit progressivement des expressions régulières décrivant des chemins de plus en plus complexes au sein de l'automate.

1. Le Théorème de Kleene : Une Vision d'Ensemble

Avant de plonger dans l'algorithme, resituons notre objectif. Le théorème de Kleene stipule que les trois classes de langages suivantes sont identiques :

Les langages reconnus par un Automate Fini Déterministe (AFD).
Les langages reconnus par un Automate Fini Non Déterministe (AFN).
Les langages décrits par une expression régulière.

Le diagramme suivant illustre les relations que nous établissons.

Diagramme du Théorème de Kleene — Ce diagramme illustre le cycle de conversions qui prouve l'équivalence entre expressions régulières, AFN et AFD. La leçon précédente couvrait la flèche "Expression Régulière → AFN". Aujourd'hui, nous nous concentrons sur la flèche "AFD → Expression Régulière", complétant ainsi la preuve.

La leçon d'aujourd'hui ferme cette boucle en montrant qu'un langage reconnu par un automate peut toujours être décrit par une expression régulière.

2. L'Algorithme de Kleene : Une Construction par Induction

L'idée centrale de l'algorithme est de construire des expressions régulières pour les ensembles de mots qui permettent de passer d'un état $q_{i}$ à un état $q_{j}$ en n'utilisant qu'un sous-ensemble restreint d'états intermédiaires. On enrichit ensuite progressivement ce sous-ensemble jusqu'à pouvoir utiliser tous les états de l'automate.

Introduction à l'algorithme de Kleene pour la conversion d'automates en expressions régulières — Cette image illustre l'environnement d'enseignement pour des concepts avancés comme la conversion d'automates en expressions régulières, au cœur de notre leçon.

Pour formaliser cela, nous allons définir une expression $R (i, j, k)$ .

Définition Formelle

Soit un automate dont les états sont numérotés de 1 à $n$ . Nous définissons $R (i, j, k)$ comme une expression régulière décrivant l'ensemble de tous les mots qui permettent de passer de l'état $q_{i}$ à l'état $q_{j}$ en utilisant uniquement des états intermédiaires dont l'indice est strictement inférieur à $k$ .

La construction se fait par récurrence sur $k$ .

Cas de base ( $k = 1$ ): $R (i, j, 1)$ décrit les chemins de $q_{i}$ à $q_{j}$ n'utilisant aucun état intermédiaire (indice < 1). Cela correspond donc aux transitions directes.
- Si $i \neq = j$ , $R (i, j, 1)$ est la somme (+) des étiquettes de toutes les flèches allant directement de $q_{i}$ à $q_{j}$ . S'il n'y en a pas, l'expression est $\emptyset$ .
- Si $i = j$ , $R (i, i, 1)$ est $ϵ$ (pour le chemin de longueur nulle) + la somme des étiquettes de toutes les boucles sur $q_{i}$ .
Étape d'induction ( $k \to k + 1$ ): Pour calculer $R (i, j, k + 1)$ , on considère les chemins de $q_{i}$ à $q_{j}$ utilisant des états intermédiaires d'indice $< k + 1$ (c'est-à-dire dans ${q_{1}, \dots, q_{k}}$ ). Un tel chemin peut :
1. Soit ne jamais passer par l'état $q_{k}$ . Dans ce cas, il n'utilise que des états intermédiaires d'indice $< k$ . L'expression correspondante est donc $R (i, j, k)$ .
2. Soit passer par l'état $q_{k}$ au moins une fois. Ce chemin se décompose en :
  - Un premier segment de $q_{i}$ à $q_{k}$ (sans passer par $q_{k}$ en intermédiaire) : $R (i, k, k)$ .
  - Zéro, une ou plusieurs boucles depuis $q_{k}$ vers $q_{k}$ (sans repasser par $q_{k}$ en intermédiaire) : $(R (k, k, k))^{*}$ .
  - Un dernier segment de $q_{k}$ à $q_{j}$ (sans passer par $q_{k}$ en intermédiaire) : $R (k, j, k)$ .

En combinant ces deux cas, on obtient la relation de récurrence fondamentale :
$R (i, j, k + 1) = R (i, j, k) + R (i, k, k) (R (k, k, k))^{*} R (k, j, k)$

La vidéo suivante, d'un cours de l'Université de Cambridge, explique cette construction de manière très rigoureuse et visuelle.

Kleene's Theorem (b): from automaton to regex (Discrete Mathematics: Formal Languages and Automata)

Cette vidéo de Frank Stajano décompose magistralement la preuve. Elle introduit le lemme puissant sur lequel repose l'algorithme, puis détaille la construction inductive (cas de base et étape de récurrence). C'est une excellente ressource pour saisir l'ingéniosité de la méthode.

Regardez les sections suivantes : De 05:40 à 12:04 : Introduction du lemme central et comment il permet de résoudre le problème. De 12:58 à 16:26 : Explication du cas de base (chemins directs, k=1). De 16:26 à 22:14 : Explication détaillée de l'étape inductive, qui est la formule que nous venons de voir. Concentrez-vous sur le raisonnement qui décompose les chemins.

Expression Finale

Une fois que nous pouvons calculer $R (i, j, k)$ pour n'importe quelles valeurs, l'expression régulière pour l'automate entier (avec $n$ états) est la somme de toutes les expressions $R (i, j, n + 1)$ où $q_{i}$ est un état initial et $q_{j}$ est un état final.
$L (A) = \sum_{q_{i} \in I, q_{j} \in F} R (i, j, n + 1)$
Le $k = n + 1$ garantit que tous les états ${q_{1}, \dots, q_{n}}$ peuvent être utilisés comme intermédiaires.

Pour une référence écrite en français, vous pouvez consulter le document suivant.

[PDF] IF114 – Automates finis et applications

Ce polycopié de cours de Bordeaux INP formalise l'algorithme sous le nom de construction de McNaughton et Yamada. C'est une excellente référence textuelle pour la formule et son application.

Lisez la section 3.3.3 "Des automates finis aux expressions régulières" (pages 38-39). Repérez la définition formelle de R(i, j, k), la formule du cas de base (3.1) et la formule de l'étape d'induction (3.2). Notez la formule finale (3.3) qui combine les résultats pour obtenir l'expression du langage.

3. Application de l'Algorithme : Un Exemple Détaillé

L'application manuelle de la formule est un processus mécanique mais qui peut vite devenir complexe en raison de la taille des expressions générées. La vidéo suivante montre un exemple complet, pas à pas. Bien qu'elle utilise une notation légèrement différente ( $R_{ij}^{k}$ au lieu de $R (i, j, k + 1)$ ), le principe est rigoureusement identique.

TOC Lec 17 - DFA to Regular expression by Deeba Kannan

Cette vidéo de Deeba Kannan est un tutoriel purement procédural. Elle est parfaite pour comprendre comment appliquer les formules, gérer les simplifications d'expressions et arriver au résultat final.

Regardez la vidéo à partir de 01:50 jusqu'à la fin. Observez attentivement les étapes : Calcul des expressions pour k=0 (transitions directes). Application de la formule pour k=1, en substituant les expressions déjà calculées. Simplification des expressions régulières obtenues (ex: a + ab = ab). Répétition du processus pour k=2 afin d'obtenir l'expression finale.

L'autre approche, visuellement équivalente, consiste à voir l'algorithme comme une élimination successive d'états dans un automate où les transitions sont étiquetées par des expressions régulières. À chaque fois qu'on élimine un état $q_{k}$ , on met à jour les transitions entre ses voisins pour prendre en compte les chemins qui passaient par $q_{k}$ , en utilisant précisément la formule $R_{ik} (R_{k k})^{*} R_{k j}$ . Le document de cours de l'enseignant-chercheur Alexis Nasr (LINK, section "Automate ⇒ expression régulière") illustre bien cette perspective graphique.

4. Exercice d'Application

Mettons en pratique la méthode d'élimination d'états, qui est souvent plus rapide à la main. Soit l'automate suivant, qui reconnaît les mots sur ${a, b}$ contenant un nombre pair de a.

États : $q_{0}$ (initial et final), $q_{1}$
Transitions :
- $δ (q_{0}, a) = q_{1}$
- $δ (q_{0}, b) = q_{0}$
- $δ (q_{1}, a) = q_{0}$
- $δ (q_{1}, b) = q_{1}$

Notre but est de trouver l'expression régulière en éliminant l'état $q_{1}$ .

Identifier les chemins passant par $q_{1}$ :
Le seul chemin qui "sort" de l'ensemble ${q_{0}}$ pour y revenir passe par $q_{1}$ . C'est le chemin $q_{0} \to q_{1} \to q_{0}$ .
Construire la nouvelle transition :
- Chemin de $q_{0}$ à $q_{1}$ : étiquette a.
- Boucles sur $q_{1}$ : étiquette b. L'expression pour passer un temps arbitraire sur $q_{1}$ est donc b*.
- Chemin de $q_{1}$ à $q_{0}$ : étiquette a.
Le chemin complet $q_{0} \to q_{1} \to \dots \to q_{1} \to q_{0}$ est donc décrit par l'expression a b* a.
Mettre à jour l'automate :
On peut maintenant "supprimer" $q_{1}$ et ajouter une nouvelle boucle sur $q_{0}$ avec l'étiquette a b* a.
L'état $q_{0}$ avait déjà une boucle étiquetée b.
Expression finale :
Après élimination de $q_{1}$ , nous n'avons plus que l'état $q_{0}$ . Le langage est l'ensemble des mots qui nous font partir de $q_{0}$ et revenir à $q_{0}$ . Ces mots sont des séquences de "boucles" sur $q_{0}$ .
Les boucles possibles sont soit b, soit a b* a. L'expression pour une boucle quelconque est donc b + a b* a.
Comme on peut faire ces boucles autant de fois que l'on veut (y compris zéro fois, pour le mot vide $ϵ$ ), l'expression finale est :
$(b + a b^{*} a)^{*}$
Ceci est bien l'expression régulière pour les mots contenant un nombre pair de a.

Conclusion

Cette leçon clôt le chapitre sur l'équivalence des formalismes des langages réguliers.

Points clés à retenir :

Le théorème de Kleene établit l'équivalence formelle entre les automates finis et les expressions régulières.
L'algorithme de Kleene (ou méthode d'élimination d'états) fournit une construction systématique pour convertir tout automate fini en une expression régulière équivalente.
La méthode repose sur une construction inductive (ou de programmation dynamique) qui calcule les expressions pour des chemins de plus en plus généraux.
La formule de récurrence $R (i, j, k + 1) = R (i, j, k) + R (i, k, k) (R (k, k, k))^{*} R (k, j, k)$ est au cœur de la preuve et de l'algorithme.

Avec la construction de Thompson et celle de Kleene, vous disposez maintenant de la boîte à outils complète pour naviguer entre ces deux représentations.

Dans notre prochaine leçon, nous aborderons un outil essentiel pour prouver qu'un langage n'est pas régulier : le lemme de pompage. Ce sera notre premier pas vers la compréhension des limites de ce modèle de calcul.

Recommended resources