Algorithme de Moore de minimisation d'un automate fini

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Dans cet automate, tous les états sont accessibles, les états c, d et e sont indistinguables, ainsi que les états a et b.

L'algorithme de Moore de minimisation d'un automate fini est un algorithme qui calcule l'automate fini déterministe complet minimal équivalent à un automate fini déterministe complet donné. Il est attribué à Edward F. Moore[1]. L'algorithme est simple à décrire, facile à programmer, et efficace en moyenne et dans le pire des cas. Il figure dans les manuels usuels d'informatique théorique[2].

Principe de l'algorithme[modifier | modifier le code]

L'algorithme de Moore opère par raffinement d'une partition des états de l’automate donné. L'algorithme maintient une partition des états, constituée initialement de deux classes, l'une formée des états terminaux et l'autre des autres états[3]. La partition est ensuite raffinée jusqu'à obtenir une partition stable. Le raffinement consiste à trouver des états séparables au sens suivant : deux états et sont séparables ou distinguables s'il existe un mot tel que l'état est final et n'est pas final, ou vice-versa. Dans le cas de l'algorithme de Moore, on remplace à chaque étape la partition courante par la partition qui est son intersection avec les partitions induites par les pré-images des classes par les lettres de l'alphabet.

Lorsque l'algorithme de raffinement s'arrête, chaque classe de la partition représente un ensemble d'états deux-à-deux inséparables, et deux classes distinctes sont séparables. L'automate minimal est obtenu en prenant comme états les classes de la partition, et comme transitions les transitions induites sur les classes par les transitions de l'automate de départ.

Description de l'algorithme[modifier | modifier le code]

On considère un automate fini déterministe complet

sur un alphabet . Ici est l'ensemble des états, est l'état initial, est l'ensemble des états terminaux. La fonction de transition est notée par un simple point. On suppose que tous les états sont accessibles[4].

L'algorithme est décrit par le pseudo-code suivant :

P := {T, Q \ T};                                           
répéter  
    P' := P                                              
    pour tout a de A faire
       calculer le raffinement de P induit par a; 
    remplacer P par son intersection avec ces raffinements        
jusqu'à P=P'

Plus formellement, on introduit une suite de relations d'équivalences sur l’ensemble des états, notées sur l’ensemble des états. Ces équivalences sont définies par

,

.

Les équivalences sont parfois appelées équivalences de Moore d'ordre [5]. Chaque ensemble est composé des mot de longueur au plus qui mènent de l'état à un état terminal de l’automate. Deux états sont équivalents pour la relation si les mêmes mots de longueur au plus mènent à des états terminaux. Par exemple, la relation a deux classes, formées respectivement par les états terminaux et non terminaux. En fait, le langage est soit vide (si p n'est pas terminal), soit réduite au mot vide (si p est terminal). Plus généralement, dire que deux états sont dans la même classe d'équivalence de Moore d'ordre signifie que l'on ne peut pas séparer les deux états par des mots de longueur au plus . Ce qui fait l’intérêt de ces équivalences est qu'ils se calculent facilement par récurrence grâce à la propriété suivante : Pour deux états et et , on a

et pour toute lettre .

Ainsi, pour calculer l'équivalence , on détermine les états qui, par une lettre, arrivent dans des classes distinctes de  : ceux-ci sont dans des classes distinctes de . Pratiquement on prend les lettres de l’alphabet l'une après l'autre ; pour une lettre , on calcule la partition dont les classes sont constituées d'états qui, par la lettre , donnent des états équivalents pour . On forme ensuite l'intersection de ces partitions avec la partition elle-même.

Il est facile de vérifier que si et sont égales pour un entier , alors et sont égales pour tout , et que les classes d'équivalences sont formées d'états inséparables.

Un premier exemple[modifier | modifier le code]

Automate minimal équivalent à l'automate du haut de la page. Les états sont les classes de l'équivalence de Moore d'ordre 2.

L'exemple donné au début de la page est un automate à six états, sur l’alphabet {0,1}. Il n'est pas difficile de calculer directement les six langages  : On a

et les états se répartissent en trois classes d'états indistinguables, donnant la partition (a,b|c,d,e|f). On peut aussi facilement calculer les langages  : On a

,
,
.

La partition de départ, définie par l'équivalence , est composée des classes et , notée . La partition induite par les images, par la lettre 1, est la partition . De même, les états dont l'image, par la lettre 0, est un état final, sont , la partition est . L'intersection de ces deux partitions est la partition . L'intersection avec la partition de donne , qui est la partition de . Pour calculer la partition suivante, on calcule la partition des images par 0 et aussi par 1, des classes de . Ce sont des classes déjà entièrement contenues dans ces classes ; on a donc . Ceci confirme le calcul ci-dessus des et . L'automate minimal a donc ces trois états ; il est donné dans la figure ci-contre.

Un deuxième exemple[modifier | modifier le code]

Un automate à minimiser.

On considère l’automate ci-contre à 8 états numérotés de 0 à 7, et sur un alphabet à deux lettres a et b. La table de transition est formée des deux premières colonnes du tableau ci-dessous. L'état initial est 0, les états 0,3,4,6,7 sont terminaux. L'équivalence est composée de deux classes, celle des états terminaux et celle des états non terminaux. On note A={0,3,4,6,7} et B={1,2,5} ces deux classes. Sur le tableau, elles sont représentées par une colonne supplémentaire.

a b a b a b
0 2 1 A B B X Z Y
1 2 1 B B B Y Z Y
2 3 2 B A B Z T Z
3 5 4 A B A T Z T
4 5 4 A B A T Z T
5 6 5 B A B Z T Z
6 5 7 A B A T Z T
7 5 7 A B A T Z T

Les colonnes suivantes sont indicées par a et b. Pour chaque ligne et chaque colonne , l'entrée contient la classe à laquelle appartient l'état . On obtient deux colonnes supplémentaires. Sur chaque ligne, le triplet de classes correspond à une intersection de classes de la partition de qui est l'intersection de la partition de avec les images inverses de ses classes par les lettres. Il y a quatre triplets : (A,B,B), (B,B,B) (B,A,B) et (A,B,A). L'équivalence a donc les quatre classes . On les note X, Y, Z, T. On répète l'opération, avec les nouvelles classes. On constate alors que les nouveaux triplets sont encore au nombre de quatre : (X,Z,Y), (Y,Z,Y), (Z,T,Z) et (T,Z,T). L'équivalence a donc les quatre même classes. L'automate minimal a donc quatre états, et les trois dernières colonnes et les quatre premières lignes de la table donnent la table de sa fonction de transition.

Complexité[modifier | modifier le code]

La complexité en temps de l'algorithme est, dans le pire des cas, , où est la taille de l'alphabet et où est le nombre d'états de l'automate. Chacune des étapes du raffinement peut être effectuée en temps en utilisant une variante appropriée du tri par base ou « radix sort ». À chaque étape, le nombre de classes augmente strictement, et comme au départ il y a deux classes, au plus étapes suffisent. En fait, la complexité est même en , où est le nombre d'étapes de l'algorithme. On peut observer[5] que le nombre d'étapes est indépendant du nombre d'états de l'automate de départ. En effet, chaque état d'un automate reconnaissant un langage correspond à un résiduel pour un mot . L'algorithme consiste donc à identifier ces langages - les mêmes pour chaque automate - en calculant leurs mots par longueur croissante.

La complexité en moyenne est bien meilleure. Elle est en , et même en , selon le choix du modèle retenu pour la distribution aléatoire[5].

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

  1. Moore 1956
  2. Carton 2008, Sakarovitch 2003, Séébold 1999, Hopcroft, Motwani et Ullman 2007.
  3. Les cas où tous les états sont terminaux ou, au contraire, où aucun ne l’est, est vite traité : l’automate minimal n'a qu'un seul état.
  4. Un état est accessible s'il existe un mot tel que , il est inaccessible sinon. Les états inaccessibles peuvent être supprimés sans modifier le langage reconnu par l'automate, et l'automate minimal ne possède que des états accessibles.
  5. a, b et c Berstel et al. 2010.

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Article de Moore
  • Edward F. Moore, « Gedanken-experiments on sequential machines », dans Automata studies, Princeton, N. J., Princeton University Press, coll. « Annals of mathematics studies » (no 34), (Math Reviews 0078059), p. 129–153.
Manuels
Article de synthèse
  • Jean Berstel, Luc Boasson, Olivier Carton et Isabelle Fagnot, « Minimization of Automata », dans Automata: from Mathematics to Applications, European Mathematical Society, (arXiv 1010.5318)
Article
  • (en) Norbert Blum, « An O(n log n) implementation of the standard method for minimizing n-state finite automata », Information Processing Letters, vol. 57, no 2,‎ , p. 65–69 (DOI 10.1016/0020-0190(95)00199-9).