Voir la source de Algorithme de McNaughton et Yamada

En [[informatique théorique]], et notamment en théorie des [[automate fini|automates finis]], l{{'}}'''algorithme de McNaughton et Yamada''' est un [[algorithme]] pour calculer une [[expression régulière]] à partir d'un automate fini. 

== Origine ==
Il porte le nom de [[Robert McNaughton]] et [[Hisao Yamada]], deux scientifiques américain et japonais qui ont décrit l'algorithme<ref name=":0">{{harvsp|McNaughton|Yamada|1960}}.</ref>. Cet algorithme est également appelé algorithme de Kleene{{Référence souhaitée|date=9 juin 2024}}.

On appelle également ''algorithme de McNaughton et Yamada'' un autre algorithme, donné dans le même article<ref name=":0" />, qui permet de construire un automate sans [[epsilon transition]] à 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 [[Algorithme de Floyd-Warshall|l’algorithme de Floyd-Warshall]] sur les graphes, où à chaque nouvelle étape, on s’autorise à passer par un nouveau sommet fixé.

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

On note <math>L_{p,q}</math> l'ensemble des mots qui sont étiquettes de chemins de <math>p</math> à <math>q
</math>. Le langage <math>L</math> reconnu par l'automate est l'ensemble
:<math>L=\bigcup_{i\in I}\bigcup_{t\in T} L_{i,t}</math>
L'algorithme de McNaugthon et Yamada est une méthode pour calculer des expressions régulières pour les <math>L_{p,q}</math>.

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

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

Pour <math>k=0</math>, 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 <math>p</math> à <math>q</math> (on ignore un chemin de longueur 0 en un état <math>p</math>).

On a donc
:<math>L_{p,q}^{(0)} =\sum_{ (p,a,q)\in \mathcal{F}} a</math>

Pour la récurrence, on considère un chemin de <math>p</math> à <math>q</math> dont les sommets intermédiaires sont plus petits que <math>k</math>. Deux cas sont alors possibles :
# les sommets intermédiaires sont plus petits que <math>k-1</math>; alors l’étiquette est dans <math>L_{p,q}^{(k-1)}</math>;
# le chemin passe par l’état <math>k</math>. On décompose alors le chemin en parties dont les sommets intermédiaires sont plus petits que <math>k-1</math>. Pour cela, on considère chaque occurrence du sommet <math>k</math> dans ce chemin : entre deux occurrences consécutives, les sommets intermédiaires sont plus petits que k-1. On a alors la formule
::<math>L_{p,q}^{(k)} = L_{p,q}^{(k-1)} + L_{p,k}^{(k-1)} (L_{k,k}^{(k-1)})^* L_{k,q}^{(k-1)}</math>.
Il y a donc <math>n+1</math> étapes (<math>k=0,\ldots,n</math>). Chacune des étapes demande le calcul de <math>n^2</math> expressions, et la taille des expressions elles-mêmes croît avec <math>k</math>. 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 <math>L^{(k)}</math> (respectivement <math>L</math>) sous forme de matrices, dont le coefficient en <math>(i,j)</math> est <math>L_{i,j}^{(k)}</math> (respectivement <math>L_{i,j}</math>).
On a alors, pour <math>\mathcal{A}=(Q, \mathcal{F}, I, T)</math> un automate fini à <math>n</math> états sur l'alphabet <math>A</math>:

   '''Fonction''' McNaughton-Yamada(<math>\mathcal{A}</math>)
      <math>L := (\sum_{ (p,a,q)\in \mathcal{F}} a)_{ 1 \leq \mathit{p},\mathit{q} \leq n} </math>  \\à l'itération k de la [[boucle for]], cette matrice représente <math>L^{(k)}</math>
      '''for''' <math>\mathit{k} := 1</math> '''to''' <math>\mathit{n}</math>
          '''for''' <math>\mathit{p} := 1</math> '''to''' <math>\mathit{n}</math>
              '''for''' <math>\mathit{q} := 1</math> '''to''' <math>\mathit{n}</math>
                 <math>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}}</math>
      R := <math>\emptyset</math>  \\expression rationnelle à retourner
      '''for''' <math>\mathit{p}\in I</math>:
          '''for''' <math>\mathit{q} \in T</math>:
              if <math>\mathit{p}==\mathit{q}</math> then
                 R := R + <math>\varepsilon</math> + <math>L_{p,p}</math> \\on n'ajoute <math>\varepsilon</math> qu'aux <math>L_{p,p}</math> où <math>\mathit{p}\in I \cap T </math>
              else
                 R := R + <math>L_{p,q}</math>
      retourner R
   '''Fin Fonction'''

== Exemples ==
=== Un premier exemple ===
[[Fichier:Automate-synchronise.png|thumb|L'automate <math>\mathcal{A}_1</math> considéré.]]
Appliquons l'algorithme de McNaughton et Yamada à l'automate <math>\mathcal{A}_1</math> représenté.
On va utiliser la représentation matricielle introduite dans la partie précédente. On a :
* <math>L^{(0)} =\begin{pmatrix}a&b\\ \emptyset&b\end{pmatrix}</math>;
* <math>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}</math>;
* <math>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}</math>.

D'où <math>L =\begin{pmatrix}\epsilon+a^+&a^*b^+\\ \emptyset &\epsilon+b^+\end{pmatrix}=\begin{pmatrix}a^*&a^*b^+\\ \emptyset &b^*\end{pmatrix}</math>.

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

[[Fichier:A1 numerot inv.svg|thumb|L'automate <math>\mathcal{A}_1</math>, avec les états numérotés dans l'ordre inverse.]]
Considérons maintenant le même automate, mais avec une numérotation différente des états.
L'algorithme appliqué à cet automate donne :

:* <math>L^{(0)} =\begin{pmatrix}b&\emptyset \\ b&a\end{pmatrix}</math>
:* <math>L^{(1)} =\begin{pmatrix}b^+&\emptyset \\ b&a\end{pmatrix}</math>
:* <math>L^{(2)} =\begin{pmatrix}b^+&\emptyset \\ a^*b^+&a^+\end{pmatrix}</math>
:D'où <math>L=\begin{pmatrix}b^*&\emptyset \\a^*b^+&a^*\end{pmatrix}</math>.

<math>L(\mathcal{A}_1)</math> est alors dénoté par <math>L_{2,2}+L_{2,1}=a^*+a^*b^+</math>, 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 ===
[[Fichier:Exemple A2.png|thumb|L'automate <math>\mathcal{A}_2</math>.]]
Donnons maintenant l'exemple présenté dans l'ouvrage de référence de Sakarovitch<ref>{{Ouvrage|langue=en|auteur1=Jacques Sakarovitch|titre=Elements of automata theory|lieu=Cambridge|éditeur=Cambridge University Press|date=1 octobre 2009|pages totales=782|isbn=978-0-521-84425-3|bnf=420782689|passage=p.96}}</ref>. Appliquons maintenant l'algorithme à l'automate <math>\mathcal{A}_2</math>.
On a :

* <math>L^{(0)} =\begin{pmatrix}a&b\\ a&b\end{pmatrix}</math>
* <math>L^{(1)} =\begin{pmatrix}a^+&a^*b\\ a^+&a^*b\end{pmatrix}</math>
* <math>L^{(2)} =\begin{pmatrix}(a^*b)^*a^+&(a^*b)^+\\ (a^*b)^*a^+&(a^*b)^+\end{pmatrix}</math>
* <math>L=\begin{pmatrix}\varepsilon+(a^*b)^*a^+&(a^*b)^+\\ (a^*b)^*a^+&(a^*b)^*\end{pmatrix}</math>.

D'où <math>L(\mathcal{A}_2)=L_{1,1}=\varepsilon+(a^*b)^*a^+</math>.

[[Fichier:A2 numerot inv.svg|thumb|L'automate <math>\mathcal{A}_2</math>, avec les états numérotés dans l'ordre inverse.]]
De même que pour le premier exemple, appliquons à nouveau l'algorithme en changeant la numérotation des états.
On a :

* <math>L^{(0)} =\begin{pmatrix}b&a\\ b&a\end{pmatrix}</math>
* <math>L^{(1)} =\begin{pmatrix}b^+&b^*a\\ b^+&b^*a\end{pmatrix}</math>
* <math>L^{(2)} =\begin{pmatrix}(b^*a)^*b^+&(b^*a)^+\\ (b^*a)^*b^+&(b^*a)^+\end{pmatrix}</math>
* <math>L =\begin{pmatrix}(b^*a)^*b^*&(b^*a)^+\\ (b^*a)^*b^+&(b^*a)^*\end{pmatrix}</math>.

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

== Notes et références ==
{{Références}}

== Bibliographie ==
* {{Article
|langue=en
|auteur1=Robert McNaughton | auteur2=Hisao Yamada
|titre=Regular expressions and state graphs for automata
|périodique=IRE Trans. Electronic Computers
|doi=10.1109/TEC.1960.5221603
|volume=EC-9|numéro=1|mois=janvier|année=1960|pages=39-47}}.
* {{Ouvrage | langue=en | auteur1=John E. Hopcroft | auteur2=Rajeev Motwani | auteur3=Jeffrey D. Ullman | titre=Introduction to Automata Theory, Languages, and Computation | éditeur=Pearson Addison Wesley | année=2007 | pages totales=xvii+535 | isbn=978-0-321-45536-9 | isbn10=0-321-45536-3 | isbn2=0201441241 | numéro d'édition=3 <!--PARAMETRE 'numéro d’édition' N'EXISTE PAS -->}} {{commentaire biblio SRL|Section 3.2.1 ''From DFA’s to Regular Expressions'', {{p.| 93-98}}}}.
* {{en}} Jacques Sakarovitch, Elements of automata theory, [[Cambridge University Press]], {{date-|1 octobre 2009}}, 782 p. {{ISBN|978-0521844253}}, p.&nbsp;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|Informatique théorique}}

[[Catégorie:Automates finis et langages réguliers]]
[[Catégorie:Algorithme]]