Conversion d’une expression régulière en automate

Nous allons voir comment convertir n’importe quelle expression régulière en automate fini non déterministe.

Exemple

Avant de décrire l’algorithme lui-même, regardons sur un exemple de quoi il s’agit. Soit cette expression régulière : a(b|c)x^∗. En mots, nous décririons le langage que cette expression régulière dénote comme l’ensemble des mots qui commencent par la lettre « a », suivie soit de la lettre « b », soit de « c », puis d’un nombre quelconque de lettres « x ». Saurions-nous construire un automate qui accepterait ce langage ? Mais oui, regarde :

Cet automate accepte manifestement le même langage. On est alors en droit de se demander si, pour toute expression régulière, il existe un automate qui accepte le langage correspondant. Eh bien, oui.

Description de l’algorithme de conversion d’une expression régulière en automate

Nous supposons que l’entrée est une expression régulière R. D’après la partie précédente sur les expressions régulières, nous savons qu’une expression régulière peut avoir six formes différentes. Nous distinguons donc six cas :

1. R = a pour une lettre a ∈ Σ. L’expression régulière est donc une seule lettre de l’alphabet Σ sur lequel nous travaillons. Un automate qui accepterait une seule lettre a ressemblerait à ceci :

   

2. R = ϵ, le mot vide. Un automate qui accepterait le mot vide ressemblerait à ceci :

   

3. R = ∅, une expression régulière qui dénote le langage vide. Un automate qui reconnaîtrait un tel langage est celui-ci :

   

4. R = R₁ ∪ R₂, où R₁, R₂ sont des expressions régulières. Nous savons déjà que la réunion de langages réguliers est encore un langage régulier et que nous savons construire un automate qui accepte un tel langage. Autrement dit, nous supposons que nous avons des automates qui reconnaissent les langages dénotés par R₁ et R₂, et nous les utilisons pour construire un automate qui accepte le langage dénoté par R₁ ∪ R₂. Exemple : si R₁ = a et R₂ = ϵ, la méthode nous donne cet automate :

   

5. R = R₁ ∘ R₂, où R₁, R₂ sont des expressions régulières. C’est le même cas que dans le point précédent. La concaténation de langages réguliers est un langage régulier, et nous savons donc construire un automate qui acceptera un tel langage. Ainsi, si R₁ = a et R₂ = b, la concaténation ressemblerait à ceci :

   

6. $R=(R_1^{\ast })$, où R₁ est une expression régulière. Là encore, nous savons que l’étoile d’un langage régulier est un langage régulier. Ainsi, si R = a^∗, l’automate ressemblerait à ceci :

   

En appliquant ces points l’un après l’autre, nous convertissons toute l’expression régulière en automate fini.

Exemple complet

Essayons de convertir l’expression régulière (a|bc)^∗. Nous obtenons successivement ces automates :

L’automate résultant accepte le langage dénoté par l’expression régulière (a|bc)^∗. Bien sûr, cet automate est terriblement compliqué, et il existe certainement un automate beaucoup plus simple qui accepte le même langage. Nous pouvons utiliser l’algorithme de déterminisation d’un AFN, puis effectuer la minimisation de l’automate.

Sources

• M. Sipser : Introduction to the Theory of Computation
• Aho, Sethi, Ullman : Compilers: Principles, Techniques, and Tools