Algorithme de Thompson : Regex vers AFN

Bonjour,

Dans la leçon précédente, nous avons appris à décrire un langage régulier à l'aide d'une expression régulière, un formalisme algébrique concis. Nous avons ainsi établi une troisième caractérisation pour la classe des langages réguliers, s'ajoutant aux automates finis déterministes (AFD) et non déterministes (AFN).

Aujourd'hui, nous allons commencer à démontrer l'équivalence formelle de ces formalismes, un pilier de la théorie des langages connu sous le nom de théorème de Kleene. Cette leçon se concentre sur la première moitié de la preuve : montrer que tout langage descriptible par une expression régulière est reconnaissable par un automate.

L'objectif est donc de maîtriser une méthode algorithmique et systématique pour convertir une expression régulière en un automate fini non déterministe (AFN). Nous utiliserons pour cela la construction de Thompson, un algorithme élégant et fondamental pour le concours de l'agrégation.

1. Le Principe de la Construction de Thompson

L'idée centrale de la construction de Thompson est d'exploiter la nature récursive des expressions régulières. Une expression régulière est définie inductivement à partir de cas de base (un symbole, le mot vide, le langage vide) et de cas récursifs (union, concaténation, étoile). L'algorithme suit cette même structure :

Cas de base : On définit des automates "briques" très simples pour les expressions élémentaires : $\emptyset$ , $ϵ$ , et a (pour un symbole a de l'alphabet).
Cas récursifs : On définit des règles de composition pour construire un automate plus complexe à partir des automates correspondant à ses sous-expressions. Chaque opération (union, concaténation, étoile) a sa propre règle de "plomberie" d'automates.

Pour que ces compositions fonctionnent de manière fiable, les automates générés par l'algorithme de Thompson respectent un invariant crucial :

Chaque automate possède un unique état initial (sans transition entrante) et un unique état final (sans transition sortante).

Cet invariant garantit que l'on peut "brancher" des automates les uns aux autres sans effets de bord. L'automate résultant est un AFN avec des transitions spontanées (un $ϵ$ -AFN).

2. Les Règles de Construction

Voyons maintenant comment construire ces automates, étape par étape. Les documents suivants, issus de cours de l'ENS Paris-Saclay et de l'EPITA, formalisent ces règles de manière rigoureuse.

[PDF] Notes de révision : Automates et langages

Ces notes de cours de l'ENS Paris-Saclay présentent de manière synthétique et formelle la construction de Thompson. C'est la référence principale pour les schémas de construction.

Lisez la section 1.2.1, "Construction de THOMPSON". Concentrez-vous sur les schémas qui illustrent la construction par induction pour les cas de base (∅, ε, a) et les opérations (E∗, E1+E2, E1E2). L'invariant sur l'unicité des états initiaux et finaux est la clé de la modularité de la méthode.

Synthétisons ces règles.

Cas de Base

Expression $\emptyset$ : Un automate sans chemin de l'état initial à l'état final. Il ne reconnaît aucun mot.
Expression $ϵ$ : Un automate où l'état initial est relié à l'état final par une unique transition spontanée.
Expression a (pour $a \in Σ$ ): Un automate où l'état initial est relié à l'état final par une unique transition étiquetée a.

L'image suivante, extraite d'un autre document de cours, visualise clairement ces trois briques de base ainsi que les règles de composition.

Thompson's Construction Algorithm for Regular Expressions to NFA — Cette image illustre les cinq règles de base de la construction de Thompson : les automates pour le mot vide (empty string), un caractère, l'union, la concaténation et l'étoile de Kleene (closure).

Cas Récursifs

Supposons que nous ayons déjà construit les automates $A_{1}$ et $A_{2}$ pour les expressions $E_{1}$ et $E_{2}$ .

Union ( $E_{1} + E_{2}$ ): On crée un nouvel état initial et un nouvel état final. Le nouvel état initial est relié par des $ϵ$ -transitions aux anciens états initiaux de $A_{1}$ et $A_{2}$ . Les anciens états finaux de $A_{1}$ et $A_{2}$ sont reliés au nouvel état final par des $ϵ$ -transitions. Cela crée un "parallélisme" : on reconnaît un mot si celui-ci est reconnu soit par $A_{1}$ , soit par $A_{2}$ .
Concaténation ( $E_{1} E_{2}$ ): On met les automates en "série". L'état final de $A_{1}$ est fusionné (ou relié par une $ϵ$ -transition) à l'état initial de $A_{2}$ . L'état initial du nouvel automate est celui de $A_{1}$ , et l'état final est celui de $A_{2}$ .
Étoile de Kleene ( $E^{*}$ ):
1. On crée un nouvel état initial et un nouvel état final.
2. On ajoute une $ϵ$ -transition du nouvel état initial au nouvel état final (pour reconnaître le mot vide $ϵ$ ).
3. On ajoute une $ϵ$ -transition du nouvel état initial à l'ancien état initial de $A$ .
4. On ajoute une $ϵ$ -transition de l'ancien état final de $A$ au nouvel état final.
5. Enfin, on ajoute une $ϵ$ -transition de l'ancien état final vers l'ancien état initial (pour permettre la répétition, le "bouclage").

3. Application sur un Exemple Complet

Appliquons ces règles pour construire l'automate de l'expression $(a + b)^{*} a$ . La vidéo suivante illustre une démarche similaire sur un autre exemple, ce qui vous aidera à visualiser le processus.

Regex to NFA Conversion Isn't Hard! (Sipser 1.28a)

Cette vidéo de la chaîne Easy Theory, bien qu'en anglais, est excellente pour sa clarté visuelle. Elle décompose la construction d'un automate pour (a ∪ abb*)*b, en suivant rigoureusement les règles que nous venons de voir. L'approche est algorithmique et facile à suivre.

Regardez l'intégralité de cette courte vidéo. L'auteur applique les règles pour la concaténation (02:17), l'étoile (03:49) et l'union (06:00). Observez comment chaque étape consiste à combiner des automates plus petits en de nouveaux automates qui respectent toujours l'invariant (un début, une fin).

Maintenant, construisons l'automate pour $(a + b)^{*} a$ à la main.

Briques de base : On commence par les automates pour a et b.
- $A (a)$ : $i_{1} a f_{1}$
- $A (b)$ : $i_{2} b f_{2}$
Union ( $a + b$ ): On combine $A (a)$ et $A (b)$ en parallèle.

Un automate pour (a+b) obtenu en appliquant la règle de l'union aux automates de base pour 'a' et 'b'.
Étoile ( $(a + b)^{*}$ ): On applique la règle de l'étoile à l'automate précédent.

Un automate pour (a+b) obtenu en appliquant la règle de l'étoile de Kleene.*
Concaténation ( $(a + b)^{*} a$ ): On met en série l'automate pour $(a + b)^{*}$ et un nouvel automate pour a.

L'automate final pour (a+b)a, obtenu par concaténation de l'automate pour (a+b) et de l'automate pour 'a'.

L'automate obtenu, bien que correct, est complexe et rempli de transitions spontanées. Les étapes suivantes (hors du cadre de cette leçon) consisteraient à éliminer ces transitions puis à déterminiser l'automate pour obtenir un AFD minimal. L'essentiel ici est la nature systématique et correcte de la construction.

4. Mise en Pratique

Il est temps de vous exercer. La feuille d'exercices suivante, classique pour ce niveau d'étude, propose plusieurs expressions à convertir.

TD 7: Algorithme de Thompson, résiduels, automate minimal — Cette feuille de TD de l'Université Paris Diderot contient des exercices typiques de l'agrégation sur la conversion d'expressions régulières en automates.

Je vous propose de réaliser l'Exercice 1, question 1 de ce document :

Appliquer l'algorithme de Thompson pour construire un $ϵ$ -AFN qui reconnaît le langage dénoté par l'expression régulière $(a ∣ b)^{*} abb$ .

Prenez une feuille et un crayon, et appliquez méthodiquement les règles que nous avons vues. Décomposez l'expression :

Commencez par a et b.
Construisez a|b.
Appliquez l'étoile pour obtenir $(a ∣ b)^{*}$ .
Construisez l'automate pour abb par deux concaténations successives.
Concaténez finalement l'automate de $(a ∣ b)^{*}$ avec celui de abb.

Cette démarche, bien que pouvant paraître fastidieuse, est la garantie d'une construction correcte et constitue une compétence algorithmique fondamentale.

Conclusion

Aujourd'hui, nous avons franchi une étape décisive en établissant un pont constructif entre le monde algébrique des expressions régulières et le monde machine des automates.

Points clés à retenir :

L'algorithme de Thompson permet de convertir n'importe quelle expression régulière en un $ϵ$ -AFN équivalent.
C'est un algorithme récursif qui suit la structure de l'expression régulière, avec des règles pour les cas de base et pour chaque opérateur (union, concaténation, étoile).
L'invariant clé est que chaque automate généré possède un unique état initial et un unique état final, ce qui permet des compositions propres.
Le résultat est un automate souvent non optimal mais garanti correct, qui peut ensuite être optimisé (élimination des $ϵ$ -transitions, déterminisation, minimisation).

Dans la prochaine leçon, nous achèverons la preuve du théorème de Kleene en étudiant la direction inverse : comment convertir un automate fini en une expression régulière. Nous verrons que cette direction est également algorithmique, bien que conceptuellement différente. Cela consolidera définitivement l'équivalence de ces trois formalismes pour décrire les langages réguliers.

Recommended resources