Algorithme de McNaughton et Yamada — Wikipédia

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.

Il 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^{[réf. souhaitée]}.

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 transition à partir d'une expression régulière.

É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é.

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.

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 

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.

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.

• (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

• 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