Voir la source de Algorithme de Moore de minimisation d'un automate fini

{{article principal|Minimisation d'un automate fini déterministe}}
[[File:DFA to be minimized.svg|thumb|upright=1.5|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]]<ref>{{harvsp|Moore|1956}}</ref>. 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<ref>{{harvsp|Carton|2008}}, {{harvsp|Sakarovitch|2003}}, {{harvsp|Séébold|1999}},  {{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007}}.</ref>.

== Principe de l'algorithme ==

L'algorithme de Moore opère par raffinement d'une [[partition (mathématiques)|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<ref>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.</ref>.  La partition est ensuite raffinée jusqu'à obtenir une partition stable. Le raffinement consiste à trouver des états séparables au sens suivant : deux états <math>p</math> et <math>q</math> sont '''séparables''' ou '''distinguables''' s'il existe un mot <math>w</math> tel que l'état <math>p\cdot w</math> est  final et <math>q\cdot w</math> 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 
:<math>\mathcal{A} = (Q, i, T)</math> 
sur un alphabet <math>A</math>. Ici <math>Q</math> est l'ensemble des états, <math>i</math> est l'état initial, <math>T</math> 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''<ref>Un état <math>q</math> est ''accessible'' s'il existe un mot <math>w</math> tel que <math>q=i\cdot w</math>, 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.</ref>. 

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  <math>\sim_0, \sim_1, \ldots</math> Ces équivalences sont définies par
:<math>p\sim_h q \iff L_q^{(h)}(\mathcal{A})=L_p^{(h)}(\mathcal{A})</math>,
où
:<math>L_p^{(h)}(\mathcal{A})=\{w\in A^*\mid p\cdot w\in T \text{ et } |w|\le h\}</math>. 
Les équivalences <math>\sim_h</math> sont parfois appelées ''équivalences de Moore'' d'ordre <math>h</math><ref name="BBCF">{{harvsp|Berstel|Boasson|Carton|Fagnot|2010}}.</ref>.
Chaque ensemble <math>L_p^{(h)}</math> est composé des mots de longueur au plus <math>h</math> qui mènent de l'état <math>p</math> à un état terminal de l’automate. Deux états sont équivalents pour la relation <math>\sim_h</math> si les mêmes mots de longueur au plus <math>h</math> mènent à des états terminaux. Par exemple, la relation <math>\sim_0</math> a deux classes, formées respectivement par les états terminaux et non terminaux. En fait, le langage <math>L_p^{(0)}(\mathcal{A})</math> 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 <math>h</math> signifie que l'on ne peut pas séparer les deux états  par des mots de longueur au plus <math>h</math>.
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 <math>p</math> et <math>q</math> et <math>h\ge 0</math>, on a 
:<math>p\sim_{h+1}q\iff p\sim_hq\quad</math>   ''et''  <math>\quad p\cdot a\sim_hq\cdot a</math>  ''pour toute lettre'' <math> a\in A</math>.
Ainsi, pour calculer l'équivalence <math>\sim_{h+1}</math>, on détermine les états qui, par une lettre, arrivent dans des classes distinctes de <math>\sim_{h}</math> : ceux-ci sont dans des classes distinctes de <math>\sim_{h+1}</math>. Pratiquement on prend les lettres de l’alphabet l'une après l'autre ; pour une lettre <math>a\in A</math>, on calcule la partition dont les classes sont constituées d'états qui, par la lettre <math>a</math>, donnent des états équivalents pour <math>\sim_h</math>. On forme ensuite l'intersection de ces partitions avec la partition  <math>\sim_h</math> elle-même.

Il est facile de vérifier que si  <math>\sim_k</math> et  <math>\sim_{k+1}</math> sont égales pour un entier <math>k</math>, alors  <math>\sim_k</math> et <math>\sim_{k+r}</math> sont égales pour tout <math>r</math>, et que les classes d'équivalences sont formées d'états inséparables.

== Un premier exemple ==
[[File:Minimized DFA.svg|thumb|upright=1.5|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 <math>L_p=\{w\in A^*\mid p\cdot w\in T\}</math> : On a 
:<math>L_a=L_b=0^*10^*, L_c=L_d=L_e=0^* L_f=\emptyset</math>
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 <math>L_p^{(h)}</math> : On a
:<math>L^{(0)}_a=L^{(0)}_b=L^{(0)}_f=\emptyset, L^{(0)}_c=L^{(0)}_d=L^{(0)}_e=\varepsilon</math>,
:<math>L^{(1)}_a=L^{(1)}_b=1, L^{(1)}_f=\emptyset, L^{(1)}_c=L^{(1)}_d=L^{(1)}_e=\{\varepsilon,0\}</math>,
:<math>L^{(2)}_a=L^{(2)}_b=\{1,01\}, L^{(2)}_f=\emptyset, L^{(2)}_c=L^{(2)}_d=L^{(2)}_e=\{\varepsilon,0,00\}</math>.

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

== Un deuxième exemple ==
[[File:Un automate à minimiser.jpg|upright=2|thumb|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  <math>\sim_0</math> 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.  

::{| class="wikitable"
!
!a
!b
!<math>\sim_0</math>
!a
!b
!<math>\sim_1</math>
!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 <math>q</math> et chaque colonne <math>a</math>, l'entrée contient la classe à laquelle appartient l'état <math>q\cdot a</math>. On obtient deux colonnes supplémentaires. Sur chaque ligne, le triplet de classes correspond à une intersection de classes de la partition de <math>\sim_1</math> qui est l'intersection de la partition de <math>\sim_0</math> 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  <math>\sim_1</math> a donc les quatre classes <math>(0|1|25|3467)</math>. 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  <math>\sim_2</math> 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, <math>O(sn^2)</math>, où <math>s</math> est la taille de l'alphabet et où <math> n</math> est le nombre d'états de l'automate. Chacune des étapes du raffinement peut être effectuée en temps <math>O(sn)</math> 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 <math>n-2</math> étapes suffisent. En fait, la complexité est même en <math>O(\ell sn)</math>, où <math>\ell</math> est le nombre d'étapes de l'algorithme. On peut observer<ref name="BBCF"/> 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 <math>L</math> correspond à un résiduel <math>u^{-1}L</math> pour un mot <math>u</math>. 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 <math>O(n \log n)</math>, et même en <math>O(n\log\log n)</math>, selon le choix du modèle retenu pour la distribution aléatoire<ref name="BBCF"/>{{,}}<ref>{{Article
|langue=
|auteur1=  Arnaud Carayol | auteur2 = Cyril Nicaud
|titre= Distribution of the number of accessible states in a random deterministic automaton
|périodique= 29th International Symposiumon Theoretical Aspects of Computer Science, STACS 2012 
|éditeur = Leibniz-Zentrum fuer Informatik
|volume= 14
|numéro=
|date= 2012
|pages= 194–205
|lire en ligne= https://drops.dagstuhl.de/opus/volltexte/2012/3442/pdf/58.pdf
}}.</ref>.

== Notes et références ==
{{Références}}
{{Autres projets|commons=Category:Deterministic finite state automata| commons titre= Automate fini déterministe}}

== Articles connexes ==
* [[Algorithme de Brzozowski de minimisation d'un automate fini]]
* [[Algorithme de Hopcroft de minimisation d'un automate fini]]

== Bibliographie ==
;Article de Moore
*{{chapitre
 | nom = Moore | prénom = Edward F. | lien auteur = Edward F. Moore
 | titre chapitre = Gedanken-experiments on sequential machines
 | math reviews = 0078059
 | lieu = Princeton, N. J.
 | passage = 129–153
 | éditeur = Princeton University Press
 | collection = Annals of mathematics studies
 | numéro dans collection = 34
 | titre = Automata studies
 | année = 1956}}.
;Manuels
* {{Langages formels, calculabilité et complexité}}
* {{Introduction to Automata Theory, Languages, and Computation}}
* {{Ouvrage | langue=fr | prénom1=Jacques | nom1=Sakarovitch | titre=Éléments de théorie des automates | lieu=Paris | éditeur=Vuibert | année=2003 | pages totales=816 | isbn=978-2-7117-4807-5 | isbn10=2-7117-4807-3 | zbl=1188.68177}}
* {{Ouvrage| langue=fr| prénom1=Patrice| nom1=Séébold| titre=Théorie des automates| sous-titre=méthodes et exercices corrigés| éditeur=Vuibert| année=1999| pages totales=198| isbn=978-2-7117-8630-5}}
;Article de synthèse
*{{chapitre | prénom1=Jean | nom1=Berstel 
 | prénom2=Luc | nom2=Boasson | prénom3=Olivier | nom3=Carton 
 | prénom4=Isabelle | nom4=Fagnot | titre chapitre=Minimization of Automata | arxiv=1010.5318 
 | année=2010 | titre ouvrage=Automata: from Mathematics to Applications
 |éditeur=European Mathematical Society }}
;Article
* {{article|langue=en|nom1=Blum|prénom1=Norbert
 |titre=An O(n log n) implementation of the standard method for minimizing n-state finite automata
 |journal=Information Processing Letters|volume=57|numéro=2|année=1996|pages=65–69
 |doi=10.1016/0020-0190(95)00199-9}}.

{{palette|Automates finis et langages réguliers}}
{{Portail|Informatique théorique}}

[[Catégorie:Automates finis et langages réguliers]]
[[Catégorie:Théorie des automates]]