Algorithme de McNaughton et Yamada

En informatique théorique, et notamment en théorie des automates finis, l'algorithme de McNaughton et Yamada est un algorithme pour calculer une expression régulière à partir d'un automate fini. Elle porte le nom de Robert McNaughton et Hisao Yamada, deux scientifiques américain et japonais qui ont décrit l'algorithme^[1]. Cet algorithme est également appelé algorithme de Kleene.

On appelle également algorithme de McNaughton et Yamada un autre algorithme, donné dans le même article^[1], qui permet de construire un automate sans epsilon transitions à partir d'une expression régulière.

Principe

Étant donné un automate à n états, et dont les états sont numérotés de 1 à n, on donne une expression pour les langages composés des mots qui étiquettent les chemins de i à j, pour tout couple i, j. Cette expression est construite par récurrence au moyen d'une condition sur les chemins ; cette condition stipule que les chemins ne passent que par certains états autorisés. À chaque itération de l’algorithme, on fixe un nouvel état par lequel on s’autorise à passer. À la fin de l’algorithme, on obtient alors tous les chemins possibles.

Le fonctionnement de cet algorithme rappelle alors l’algorithme de Floyd-Warshall sur les graphes, où à chaque nouvelle étape, on s’autorise à passer par un nouveau sommet fixé.

Description

Soit ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$ un automate fini sur un alphabet ${\displaystyle A}$, donné par un ensemble fini d'états ${\displaystyle Q}$, un ensemble ${\displaystyle {\mathcal {F}}\subset Q\times A\times Q}$ de transitions, et des ensembles ${\displaystyle I,T\subseteq Q}$ d'états initiaux respectivement terminaux.

On note ${\displaystyle L_{p,q}}$ l'ensemble des mots qui sont étiquettes de chemins de ${\displaystyle p}$ à ${\displaystyle q}$. Le langage ${\displaystyle L}$ reconnu par l'automate est l'ensemble

${\displaystyle L=\bigcup _{i\in I}\bigcup _{t\in T}L_{i,t}}$

L'algorithme de McNaugthon et Yamada est une méthode pour calculer des expressions régulières pour les ${\displaystyle L_{p,q}}$.

On note ${\displaystyle L_{p,q}^{(k)}}$ l'expression pour l’ensemble des mots qui étiquettent des chemins de ${\displaystyle p}$ à ${\displaystyle q}$ et dont tous les sommets intermédiaires sont inférieurs ou égaux à ${\displaystyle k}$. Les sommets de départ ${\displaystyle p}$ et d’arrivée ${\displaystyle q}$ ne sont pas intermédiaires, donc ils ne sont pas soumis à la contrainte d’être inférieurs ou égaux à ${\displaystyle k}$.

On construit les ${\displaystyle L_{p,q}^{(k)}}$ par récurrence sur ${\displaystyle k}$, en commençant avec ${\displaystyle k=0}$, et en terminant avec ${\displaystyle k=n}$. Lorsque ${\displaystyle k=n}$, la contrainte sur ${\displaystyle k}$ n’est plus une restriction, et ${\displaystyle L_{p,q}^{(n)}=L_{p,q}}$ si ${\displaystyle p\neq q}$, et ${\displaystyle \varepsilon +L_{p,p}^{(n)}=L_{p,p}}$.

Pour ${\displaystyle k=0}$, comme les sommets sont numérotés à partir de 1, la contrainte exprime simplement qu’il n’y a pas de sommet intermédiaire. Les seuls chemins sont des transitions de ${\displaystyle p}$ à ${\displaystyle q}$ (on ignore un chemin de longueur 0 en un état ${\displaystyle p}$).

On a donc

${\displaystyle L_{p,q}^{(0)}=\sum _{(p,a,q)\in {\mathcal {F}}}a}$

Pour la récurrence, on considère un chemin de ${\displaystyle p}$ à ${\displaystyle q}$ dont les sommets intermédiaires sont plus petits que ${\displaystyle k}$. Deux cas sont alors possibles :

1. les sommets intermédiaires sont plus petits que ${\displaystyle k-1}$; alors l’étiquette est dans ${\displaystyle L_{p,q}^{(k-1)}}$;
2. le chemin passe par l’état ${\displaystyle k}$. On décompose alors le chemin en parties dont les sommets intermédiaires sont plus petits que ${\displaystyle k-1}$. Pour cela, on considère chaque occurrence du sommet ${\displaystyle k}$ dans ce chemin : entre deux occurrences consécutives, les sommets intermédiaires sont plus petits que k-1. On a alors la formule

${\displaystyle L_{p,q}^{(k)}=L_{p,q}^{(k-1)}+L_{p,k}^{(k-1)}(L_{k,k}^{(k-1)})^{*}L_{k,q}^{(k-1)}}$.

Il y a donc ${\displaystyle n+1}$ étapes (${\displaystyle k=0,\ldots ,n}$). Chacune des étapes demande le calcul de ${\displaystyle n^{2}}$ expressions, et la taille des expressions elles-mêmes croît avec ${\displaystyle k}$. S’il est facilement programmable, l’algorithme est assez pénible à la main. Il est alors utile d’utiliser les règles qui permettent de simplifier des expressions régulières.

Pseudo-code

On va représenter les ${\displaystyle L^{(k)}}$ (respectivement ${\displaystyle L}$) sous forme de matrices, dont le coefficient en ${\displaystyle (i,j)}$ est ${\displaystyle L_{i,j}^{(k)}}$ (respectivement ${\displaystyle L_{i,j}}$). On a alors, pour ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$ un automate fini à ${\displaystyle n}$ états sur l'alphabet ${\displaystyle A}$:

  Fonction McNaughton-Yamada(${\displaystyle {\mathcal {A}}}$)
     ${\displaystyle L:=(\sum _{(p,a,q)\in {\mathcal {F}}}a)_{1\leq {\mathit {p}},{\mathit {q}}\leq n}}$  \\à l'itération k de la boucle for, cette matrice représente ${\displaystyle L^{(k)}}$
     for ${\displaystyle {\mathit {k}}:=1}$ to ${\displaystyle {\mathit {n}}}$
         for ${\displaystyle {\mathit {p}}:=1}$ to ${\displaystyle {\mathit {n}}}$
             for ${\displaystyle {\mathit {q}}:=1}$ to ${\displaystyle {\mathit {n}}}$
                ${\displaystyle L_{{\mathit {p}},{\mathit {q}}}:=L_{{\mathit {p}},{\mathit {q}}}+L_{{\mathit {p}},{\mathit {k}}}(L_{{\mathit {k}},{\mathit {k}}})^{*}L_{{\mathit {k}},{\mathit {q}}}}$
     R := ${\displaystyle \emptyset }$  \\expression rationnelle à retourner
     for ${\displaystyle {\mathit {p}}\in I}$:
         for ${\displaystyle {\mathit {q}}\in T}$:
             if ${\displaystyle {\mathit {p}}=={\mathit {q}}}$ then
                R := R + ${\displaystyle \varepsilon }$ + ${\displaystyle L_{p,p}}$ \\on n'ajoute ${\displaystyle \varepsilon }$ qu'aux ${\displaystyle L_{p,p}}$ où ${\displaystyle {\mathit {p}}\in I\cap T}$
             else
                R := R + ${\displaystyle L_{p,q}}$
     retourner R
  Fin Fonction

Exemples

Un premier exemple

Appliquons l'algorithme de McNaughton et Yamada à l'automate ${\displaystyle {\mathcal {A}}_{1}}$ représenté. On va utiliser la représentation matricielle introduite dans la partie précédente. On a :

• ${\displaystyle L^{(0)}={\begin{pmatrix}a&b\\\emptyset &b\end{pmatrix}}}$;
• ${\displaystyle L^{(1)}={\begin{pmatrix}a+a(a)^{*}a&b+a(a)^{*}b\\\emptyset &b+\emptyset (a)^{*}b\end{pmatrix}}={\begin{pmatrix}a^{+}&a^{*}b\\\emptyset &b\end{pmatrix}}}$;
• ${\displaystyle L^{(2)}={\begin{pmatrix}a^{+}+(a^{*}b)(b)^{*}\emptyset &a^{*}b+(a^{*}b)(b)^{*}b\\\emptyset &b+bb^{*}b\end{pmatrix}}={\begin{pmatrix}a^{+}&a^{*}b^{+}\\\emptyset &b^{+}\end{pmatrix}}}$.

D'où ${\displaystyle L={\begin{pmatrix}\epsilon +a^{+}&a^{*}b^{+}\\\emptyset &\epsilon +b^{+}\end{pmatrix}}={\begin{pmatrix}a^{*}&a^{*}b^{+}\\\emptyset &b^{*}\end{pmatrix}}}$.

Le langage ${\displaystyle L({\mathcal {A}}_{1})}$ reconnu par ${\displaystyle {\mathcal {A}}_{1}}$est alors dénoté par l'expression rationnelle ${\displaystyle L_{1,1}+L_{1,2}=a^{*}+a^{*}b^{+}}$. Après simplifications, on a ${\displaystyle L({\mathcal {A}}_{1})=a^{*}b^{*}}$, ce qui est bien le résultat attendu.

Considérons maintenant le même automate, mais avec une numérotation différente des états. L'algorithme appliqué à cet automate donne :

• ${\displaystyle L^{(0)}={\begin{pmatrix}b&\emptyset \\b&a\end{pmatrix}}}$
• ${\displaystyle L^{(1)}={\begin{pmatrix}b^{+}&\emptyset \\b&a\end{pmatrix}}}$
• ${\displaystyle L^{(2)}={\begin{pmatrix}b^{+}&\emptyset \\a^{*}b^{+}&a^{+}\end{pmatrix}}}$

D'où ${\displaystyle L={\begin{pmatrix}b^{*}&\emptyset \\a^{*}b^{+}&a^{*}\end{pmatrix}}}$.

${\displaystyle L({\mathcal {A}}_{1})}$ est alors dénoté par ${\displaystyle L_{2,2}+L_{2,1}=a^{*}+a^{*}b^{+}}$, soit exactement la même expression rationnelle que précédemment : pour cet exemple particulier, le choix du nouvel état autorisé à chaque étape ne change pas l'expression rationnelle obtenue en fin d'algorithme.

Un deuxième exemple, où la numérotation des états change le résultat

Donnons maintenant l'exemple présenté dans l'ouvrage de référence de Sakarovitch^[2]. Appliquons maintenant l'algorithme à l'automate ${\displaystyle {\mathcal {A}}_{2}}$. On a :

• ${\displaystyle L^{(0)}={\begin{pmatrix}a&b\\a&b\end{pmatrix}}}$
• ${\displaystyle L^{(1)}={\begin{pmatrix}a^{+}&a^{*}b\\a^{+}&a^{*}b\end{pmatrix}}}$
• ${\displaystyle L^{(2)}={\begin{pmatrix}(a^{*}b)^{*}a^{+}&(a^{*}b)^{+}\\(a^{*}b)^{*}a^{+}&(a^{*}b)^{+}\end{pmatrix}}}$
• ${\displaystyle L={\begin{pmatrix}\varepsilon +(a^{*}b)^{*}a^{+}&(a^{*}b)^{+}\\(a^{*}b)^{*}a^{+}&(a^{*}b)^{*}\end{pmatrix}}}$.

D'où ${\displaystyle L({\mathcal {A}}_{2})=L_{1,1}=\varepsilon +(a^{*}b)^{*}a^{+}}$.

De même que pour le premier exemple, appliquons à nouveau l'algorithme en changeant la numérotation des états. On a :

• ${\displaystyle L^{(0)}={\begin{pmatrix}b&a\\b&a\end{pmatrix}}}$
• ${\displaystyle L^{(1)}={\begin{pmatrix}b^{+}&b^{*}a\\b^{+}&b^{*}a\end{pmatrix}}}$
• ${\displaystyle L^{(2)}={\begin{pmatrix}(b^{*}a)^{*}b^{+}&(b^{*}a)^{+}\\(b^{*}a)^{*}b^{+}&(b^{*}a)^{+}\end{pmatrix}}}$
• ${\displaystyle L={\begin{pmatrix}(b^{*}a)^{*}b^{*}&(b^{*}a)^{+}\\(b^{*}a)^{*}b^{+}&(b^{*}a)^{*}\end{pmatrix}}}$.

D'où ${\displaystyle L({\mathcal {A}}_{2})=L_{2,2}=(b^{*}a)^{*}}$ : l'expression rationnelle obtenue pour le même langage est différente.

Notes et références

Bibliographie

• (en) Robert McNaughton et Hisao Yamada, « Regular expressions and state graphs for automata », IRE Trans. Electronic Computers, vol. EC-9, n^o 1,‎ janvier 1960, p. 39-47 (DOI 10.1109/TEC.1960.5221603).
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Addison Wesley, 2007, 3^e éd., xvii+535 (ISBN 978-0-321-45536-9 et 0201441241) — Section 3.2.1 From DFA’s to Regular Expressions, p. 93-98.
• (en) Jacques Sakarovitch, Elements of automata theory, Cambridge University Press, 1^er octobre 2009, 782 p. (ISBN 978-0521844253), p. 96

Articles connexes

• Algorithme de Conway
• Méthode de Brzozowski et McCluskey
• Lemme d'Arden
• Théorème de Kleene
• Automates finis
• Langage rationnel
• Algorithme de Floyd-Warshall

• Portail de l'informatique théorique