Algorithme de Moore de minimisation d'un automate fini
![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/DFA_to_be_minimized.jpg/330px-DFA_to_be_minimized.jpg)
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
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
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 Ces équivalences sont définies par
- ,
où
- .
Les équivalences sont parfois appelées équivalences de Moore d'ordre [5]. Chaque ensemble est composé des mots 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Minimized_DFA.jpg/330px-Minimized_DFA.jpg)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Un_automate_%C3%A0_minimiser.jpg/440px-Un_automate_%C3%A0_minimiser.jpg)
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é
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],[6].
Notes et références
- ↑ Moore 1956
- ↑ Carton 2008, Sakarovitch 2003, Séébold 1999, Hopcroft, Motwani et Ullman 2007.
- ↑ 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.
- ↑ 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.
- ↑ a b et c Berstel et al. 2010.
- ↑ Arnaud Carayol et Cyril Nicaud, « Distribution of the number of accessible states in a random deterministic automaton », 29th International Symposiumon Theoretical Aspects of Computer Science, STACS 2012, Leibniz-Zentrum fuer Informatik, vol. 14, , p. 194–205 (lire en ligne).
Sur les autres projets Wikimedia :
- Automate fini déterministe, sur Wikimedia Commons
Articles connexes
- Algorithme de Brzozowski de minimisation d'un automate fini
- Algorithme de Hopcroft de minimisation d'un automate fini
Bibliographie
- 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), (MR 0078059), p. 129–153.
- Manuels
- Olivier Carton, Langages formels, calculabilité et complexité, [détail de l’édition] (lire en ligne)
- (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, , 3e éd. (ISBN 978-0-32146225-1)
- Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, , 816 p. (ISBN 978-2-7117-4807-5, zbMATH 1188.68177)
- Patrice Séébold, Théorie des automates : méthodes et exercices corrigés, Vuibert, , 198 p. (ISBN 978-2-7117-8630-5)
- 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).
v · m Automates finis et langages réguliers | |
---|---|
Articles généraux |
|
Automates finis | |
Automates finis particuliers |
|
Langages réguliers | |
Des automates aux langages | |
Des langages aux automates | |
Minimisation | |
Équivalences |
Portail de l'informatique théorique