Algorithme de McNaughton et Yamada

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme de McNaughton et Yamada est, en informatique théorique, et notamment en théorie des automates finis, 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].

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

Principe[modifier | modifier le code]

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

Description[modifier | modifier le code]

Soit un automate fini sur un alphabet , donné par un ensemble fini d'états , un ensemble de transitions, et des ensembles d'états initiaux respectivement terminaux.

On note l'ensemble des mots qui sont étiquettes de chemins de à . Le langage reconnu par l'automate est l'ensemble

L'algorithme de McNaugthon et Yamada est une méthode pour calculer des expressions régulières pour les .

On note est l'expression pour l’ensemble des mots qui étiquettent des chemins de à et dont tous les sommets intermédiaires sont inférieurs ou égaux à . Les sommets de départ et d’arrivée ne sont pas intermédiaires, donc ils ne sont pas soumis à la contrainte d’être inférieurs ou égaux à .

On construit les par récurrence sur , en commençant avec , et en terminant avec . Lorsque , la contrainte sur n’est plus une restriction, et si , et .

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

On a donc

Pour la récurrence, on considère un chemin de à dont les sommets intermédiaires sont plus petits que . Deux cas sont alors possibles :

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

Il y a donc étapes (). Chacune des étapes demande le calcul de expressions, et la taille des expressions elles-mêmes croît avec . 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.

Exemple[modifier | modifier le code]

Un automate à 2 états.

Les expressions pour les langages se groupent bien dans des matrices. On a

, puis
, et enfin
.

Explicitons le calcul de . D'après la formule générale, on a

soit

.

Notes et références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Robert McNaughton et Hisao Yamada, « Regular expressions and state graphs for automata », IRE Trans. Electronic Computers, vol. EC-9, no 1,‎ , 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, , xvii+535 p. (ISBN 0-321-45536-3 et 0201441241) — Section 3.2.1 From DFA’s to Regular Expressions, p.  93-98.