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

Nous allons voir comment convertir n’importe quel automate fini en expression régulière.

Description de l’algorithme

L’entrée est un AFN A. Dans un premier temps, nous le transformons en AFNG. Dans la seconde phase, à chaque étape nous éliminons un état, nous modifions correctement la fonction de transition et nous recommençons jusqu’à ce qu’il ne reste que deux états : l’état initial et l’état final. Entre eux passera un arc dont l’étiquette est une expression régulière, qui sera le résultat de l’algorithme tout entier. Toute la méthode consiste donc essentiellement à éliminer un état, puis à corriger l’automate de façon à obtenir un automate équivalent.

Élimination d’un état

Voyons sur un exemple simple comment éliminer un état. Supposons qu’une partie de notre automate ressemble à ceci :

où les R_i sont des expressions régulières. À quoi ressemblerait l’automate si nous éliminions l’état q_r ? On peut se l’imaginer ainsi : nous sommes dans l’état q_i et nous nous demandons quels sont tous les mots que nous pouvons engendrer sur cette portion. Si nous allons directement de l’état q_i à l’état q_j, ce seront tous les mots qui correspondent à l’expression régulière R₄.

Mais si nous passons par l’état q_r, nous pouvons engendrer les mots de la forme R₁. Dans l’état q_r, nous pouvons cependant boucler selon l’expression régulière R₂, de sorte que nous pouvons en fait engendrer les mots de la forme $R_1\circ (R_2^{\ast })$. Et comme nous pouvons encore aller de l’état q_r à l’état q_j, nous ajoutons encore l’expression régulière R₃. Au total, par ce chemin, nous pouvons obtenir les mots de la forme $R_1\circ (R_2^{\ast })\circ R_3$.

Nous savons maintenant que, de cette partie de l’automate, peuvent sortir des mots de la forme R₄ ou de la forme $R_1\circ (R_2^{\ast })\circ R_3$. Cela s’écrit bien sûr sous forme d’expression régulière : $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Nous pouvons maintenant éliminer simplement l’état q_r et ne garder que les deux états q_i et q_j, et à la place de R₄ nous écrivons l’expression que nous venons de calculer :

Nous effectuons cette opération avec chaque arc partant de chaque état q_i vers un état q_j, y compris les boucles, c’est-à-dire y compris le cas où q_i = q_j.

Après l’élimination d’un état, nous obtenons un automate équivalent, c’est-à-dire un automate qui reconnaît le même langage.

L’algorithme complet

L’entrée est un AFN A = (Q ; Σ ; δ ; q₀ ; F).

1. Nous convertissons l’AFN A en AFNG Z = (Q′ ; Σ ; δ′ ; q₀′ ; q_f′). Dans la suite, nous noterons k le nombre d’états de Z.
2. Si k = 2, l’algorithme se termine, et sur l’arc entre l’état initial et l’état final se trouve l’expression régulière cherchée.
3. Si k>2, nous choisissons un état quelconque q_r différent de l’état initial et de l’état final, c’est-à-dire q_r ≠ q₀′ et q_r ≠ q_f′. Nous construisons ensuite un nouvel AFNG Z′ = (Q′′ ; Σ ; δ′′ ; q₀′ ; q_f′) tel que : $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ et, pour tout q_i ∈ Q′′ ∖ {q_f′} et tout q_j ∈ Q′′ ∖ {q₀′}, posons $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ où R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Ensuite, retourne à l’étape 2.

Exemple

Soit en entrée cet automate fini :

Nous le convertissons d’abord en AFNG (nous ne représenterons pas les transitions ∅ inutiles) :

Appliquons maintenant la seconde partie de l’algorithme et éliminons un nœud. Commençons par le nœud q₂. Nous éliminons le nœud q₂ et nous ajoutons une transition de l’état q₁ vers l’état q_f. Nous étiquetons cette transition b(a|b)^∗, car du nœud q₁ nous arrivons à l’état q₂ par les mots de la forme b, puis nous pouvons boucler selon a|b, ce qui donne (a|b)^∗, et enfin nous passons à q_f par la ε-transition. On a en outre b(a|b)^∗ϵ = b(a|b)^∗. Nous obtenons l’automate :

Il nous reste à éliminer le dernier état, q₁. Nous ajoutons un arc de l’état q_s à l’état q_f. Comment l’étiqueter ? Nous arrivons à l’état q₁ par une ε-transition, que nous pouvons omettre directement. Ensuite, nous pouvons boucler selon a, ce qui donne l’expression régulière a^∗. Et enfin, nous arrivons à q_f par l’arc, donc nous concaténons encore l’expression avec b(a|b)^∗. Nous étiquetons donc l’arc par l’expression régulière a^∗ b(a|b)^∗.

L’automate n’a plus que deux états, donc l’algorithme se termine. Sur l’arc se trouve l’expression régulière cherchée.

Sources

• L’exemple et la description de l’algorithme proviennent de M. Sipser : Introduction to the Theory of Computation