Voir la source de Minimisation d'un automate fini déterministe

[[Fichier:DFA to be minimized.svg|vignette|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''.]]
[[Fichier:Minimized DFA.svg|vignette|upright=1.5|Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état.]]
En [[informatique théorique]], et plus particulièrement en [[théorie des automates]], la '''minimisation d'un automate fini déterministe''' est l'opération qui consiste à transformer un [[automate fini déterministe]] donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même [[langage rationnel]]. La minimisation a une importance pratique évidente par le gain d'espace qu'elle permet. Il existe plusieurs algorithmes pour effectuer cette opération de minimisation ; les plus usuels sont décrits pour la plupart dans les manuels traitant de théorie des automates<ref>{{harvsp|Carton|2008}}, {{harvsp|Sakarovitch|2003}} sont des livres standards en français, {{harvsp|Séébold|1999}} contient des exercices détaillés ; {{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007}} est une référence anglaise.</ref>.

Les algorithmes généraux les plus connus - nommés d'après leurs inventeurs - sont l'[[algorithme de Brzozowski de minimisation d'un automate fini|algorithme de Brzozowski]], l'[[algorithme de Moore de minimisation d'un automate fini|algorithme de Moore]], et l'algorithme de [[John Hopcroft|Hopcroft]]. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des [[Ensemble fini|ensembles finis]] de mots, comme l'algorithme de Revuz<ref name="BBCF"/> et ses variantes. Les algorithmes ont aussi été étendus à des cas plus généraux, comme les automates avec sortie ([[automate de Moore]], [[automate de Mealy]]) ou les [[transducteur fini|transducteurs finis]]. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les [[automate à pile|automates à pile]] ou les [[automate linéairement borné|automates linéairement bornés]].

Une application importante de la minimisation des automates finis déterministes est le test de l'équivalence de deux automates finis, c'est-à-dire le fait de décider s'ils reconnaissent le même langage. C'est une conséquence de l'unicité de l'automate fini minimal, à un renommage des états près. Pour répondre à la question, il suffit de minimiser les deux automates et de tester si leurs versions minimales sont égales.

Étant donné l'importance de la minimisation, cette opération fait partie de la plupart des logiciels de manipulation d'automates.

== Automate minimal déterministe ==
Tout langage rationnel est reconnu par un [[automate fini]] déterministe et complet, et parmi ces automates, il en existe un ayant un nombre minimal d'états<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007}}, Section 4.4.3, "Minimization of DFA's", p. 159.</ref>. Cet automate est unique au renommage des états près; c'est l’''automate minimal'' du langage. L'intérêt d'un automate minimal est que le coût en espace de la représentation est minimisé.

Parmi les automates finis reconnaissant un langage donné, il peut exister des automates non déterministes qui reconnaissent ce langage, et qui ont exponentiellement moins d'états que l'automate fini déterministe minimal. L'adjectif ''minimal'' s'applique ici aux automates déterministes<ref name="BBCF">{{harvsp|Berstel|Boasson|Carton|Fagnot|2010}}.</ref>. De même, il peut exister des automates non déterministes non isomorphes ayant un nombre minimal d'états et reconnaissant le même langage<ref name="BBCF"/>. L'unicité de l'automate déterministe minimal est donc une propriété remarquable, valable uniquement dans ce cas.

Les automates considérés dans ce cadre sont non seulement déterministes, mais aussi ''[[automate fini|complets]]''. Un automate est complet si sa fonction de transition est partout définie, en d'autres termes si, pour tout état et toute lettre, il existe une transition sortant de cet état et étiquetée par cette lettre. Un automate fini déterministe ''[[Automate fini#Automate complet.2C automate .C3.A9mond.C3.A9|émondé]]'' peut avoir un état de moins, si l'automate fini complet correspondant a un état puits.

=== États accessibles ===
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. 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. Un automate est accessible si tous ses états sont accessibles.

Les états accessibles d'un automate peuvent être calculés au moyen d'un parcours du graphe qui représente l'automate. Ce sont les états qui sont atteints par un chemin depuis l'état initial. Il suffit donc d'adapter l'algorithme usuel de parcours d'un graphe à ce cas. La [[complexité en temps]] de l'algorithme est linéaire en fonction du produit <math>\operatorname{Card}(Q)\times\operatorname{Card}(A)</math> du nombre d'états par la taille de l'alphabet. Le code suivant en est une réalisation :

{{boîte déroulante/début|titre = Calcul des états accessibles}}
<syntaxhighlight lang="ocaml">
let états_accessibles:= {i};
let états_nouveaux:= {i};
do {
    temp := l'ensemble vide;
    for each q in états_nouveaux do
        for all a in A do
            temp := temp ∪ {q.a)};
        end;
    end;
    états_nouveaux := temp \ états_accessibles;
    états_accessibles := états_accessibles ∪ états_nouveaux;
} while(états_nouveaux ≠ the empty set);
état_inaccessibles := Q \ états_accessibles;
</syntaxhighlight>
{{boîte déroulante/fin}}

=== États indistinguables ===

Soit
:<math>\mathcal{A} = (Q, i, T)</math>
un automate déterministe complet. Deux états <math>p</math> et <math>q</math> sont ''indistinguables'' ou ''inséparables'' si tout mot <math>w</math> reconnu par <math>\mathcal{A}</math> à partir de <math>p</math> est aussi reconnu à partir de <math>q</math> et réciproquement, formellement si pour tout mot <math>w</math> :
:<math>p\cdot w\in T \iff q\cdot w \in T</math>.
Deux états sont '''séparables''' s'ils ne sont pas inséparables.
Un critère de minimalité utile est le suivant :
{{théorème|Critère de minimalité| Un automate fini déterministe complet et accessible est minimal si et seulement ses états sont deux-à-deux séparables.}}
Une façon plus condensée de présenter ce critère est d'introduire les ''langages à droite'' (« right languages » en anglais<ref name="BBCF"/>) : le langage à droite d'un état <math>q</math> est par définition le langage
:<math>L_q(\mathcal{A})=\{w\in A^*\mid q\cdot w \in T\}</math>.
C'est donc l'ensemble des mots reconnus par l’automate en prenant <math>q</math> comme état initial. Alors deux états sont inséparables si et seulement s'ils ont même langage à droite.

L'[[équivalence de Nerode]] est la relation, notée <math>\sim</math>, sur l'ensemble des états définie par
:<math>q \sim q'\iff L_q(\mathcal{A}) = L_{q'}(\mathcal{A})</math> .
Deux états équivalents pour l'équivalence de Nerode sont donc indistinguables et réciproquement. Un automate est donc minimal, d'après l'énoncé ci-dessus, exactement quand son équivalence de Nerode est l’égalité.

Ne pas confondre cette équivalence, définie sur les états, avec la ''relation de Myhill-Nerode'', du [[théorème de Myhill-Nerode]], qui est définie sur les mots : deux mots sont équivalents pour la [[théorème de Myhill-Nerode|relation de Myhill-Nerode]] s'ils définissent le même résiduel ou quotient à droite. Les états de l’automate minimal sont en [[bijection]] avec les classes de l'équivalence de Myhill-Nerode.

== Un algorithme élémentaire ==
Un algorithme élémentaire de minimisation d'un automate fini déterministe consiste à chercher des paires d'états inséparables ou indistinguables. Cette méthode se trouve dans le manuel de [[John Hopcroft|Hopcroft]], [[Rajeev Motwani|Motwani]] et [[Jeffrey Ullman|Ullman]]<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|loc=Section 4.4.1}}</ref> et celui de Peter Linz<ref>{{harvsp|Linz|2011|loc=Section 2.4}}.</ref>.

=== Algorithme de recherche d'états séparables ===
La méthode est un ''algorithme de marquage''. Elle consiste à chercher et marquer des paires d'états séparables. Elle procède les paires <math>(p,q)</math> d'états distincts comme suit :
# Pour toute paire <math>(p,q)</math> d'états, si <math>p</math> est final et <math>q</math> ne l'est pas ou vice-versa, marquer <math>(p,q)</math> comme séparables.
# Répéter l'opération suivante tant qu'une nouvelle paire a été marquée :
:Pour toute paire <math>(p,q)</math> et toute lettre <math>a</math>, calculer <math>p_a=p\cdot a</math> et <math>q_a=q\cdot a</math>. Si la paire <math>(p_a,q_a)</math> est marquée comme étant séparable, marquer <math>(p,q)</math> comme séparable.
=== Méthode de remplissage de table ===
Hopcroft ''et. al.''<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|p=157}}.</ref> appellent {{Citation étrangère|langue=en|table-filling algorithm}} (« algorithme de remplissage de table ») la mise en œuvre de l'algorithme qui consiste à remplir une table par inspection progressive des cases. Dans la table ci-dessous, une croix en case (X,Y) signifie que les états X et Y sont séparables. L'exemple suivant se trouve dans leur livre :
[[Fichier:Exemple pour minimisation.jpg|vignette|upright=1.5|Exemple pour le remplissage de table. Les états terminaux sont en rose.]]
{| class="wikitable"
!
!A
!B
!C
!D
!E
!F
!G
!H
|-
|'''B'''
|x
|
|
|
|
|
|
|
|-
|'''C'''
|x
|x
|
|
|
|
|
|
|-
|'''D'''
|x
|x
|x
|
|
|
|
|
|-
|'''E'''
|
|x
|x
|x
|
|
|
|
|-
|'''F'''
|x
|x
|x
|
|x
|
|
|
|-
|'''G'''
|x
|x
|
|x
|x
|x
|
|
|-
|'''H'''
|x
|
|x
|x
|x
|x
|x
|
|}
La première étape consiste à marquer d'une croix les paires (X,Y) où X est final et Y ne l'est pas et vice-versa. Ensuite, on peut marquer l'entrée (B,A) parce que leurs images par la lettre 0 est séparable. On continue autant que possible. Les cases restées non marquées désignent des états inséparables. Ici,
cela signifie donc que A et E sont indistinguables, de même que B et H et D et F.

L'algorithme de remplissage est similaire aux autres algorithmes de raffinement décrits ci-dessous. Il est facile à mettre en œuvre à la main sur de petits exemples, mais sa complexité en place et en temps est considérable, sauf à organiser l'exploration de manière disciplinée, auquel cas on se rapproche de la [[méthode de Moore]].

== Algorithme de Brzozowski ==
{{Article détaillé|Algorithme de Brzozowski de minimisation d'un automate fini}}
Brzozowski présente, dans son article de 1963<ref>{{harvsp|Brzozowski|1963}}</ref>, un algorithme de minimisation qui est basé sur la [[automate fini|déterminisation]] d'un automate fini non nécessairement déterministe. Cet algorithme, conceptuellement simple, produit - de façon étonnante - un automate minimal.

La notion importante de l'algorithme est celle d'[[automate transposé]] : on modifie l'automate en échangeant les états finaux et initiaux, et en changeant le sens des transitions.

L'énoncé précis est le suivant :
{{théorème|Proposition (Brzozowski)|énoncé= Soit <math>\mathcal{A}</math> un automate fini déterministe et accessible, et soit <math>\mathcal{A}^\sim</math> l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé <math>\mathcal{A}^R</math> par déterminisation et élimination des états inaccessibles. Alors l'automate <math>\mathcal{A}^\sim</math> est minimal et reconnaît le langage miroir du langage reconnu par <math>\mathcal{A}</math>.}}

L'algorithme de minimisation d'un automate fini <math>\mathcal{A}</math> est alors le suivant :
# Calculer <math>\mathcal{A}^\sim</math>, en transposant l'automate puis en le déterminisant par la procédure usuelle par exemple qui ne conserve que les états accessibles;
# Répéter l'opération sur l'automate obtenu : calculer <math>(\mathcal{A}^\sim)^\sim</math> en transposant <math>\mathcal{A}^\sim</math> puis en le déterminisant de la même manière.

Pour la deuxième étape, l'automate est déterministe et accessible. Par la proposition de Brzozowski, l'automate obtenu est l'automate minimal équivalent à l’automate de départ.
La [[complexité en temps]] et en place de l'algorithme est exponentielle dans le pire des cas en fonction de la taille de l'automate de départ, car l'automate intermédiaire <math>\mathcal{A}^\sim</math> peut être exponentiel. Un exemple est fourni par le langage <math>K_n</math> formé de mots de longueur au moins <math>n</math> sur un alphabet à deux lettres <math>a</math> et <math>b</math>, et dont la <math>n</math>-ième lettre toujours un <math>a</math>, en d'autres termes :
:<math>K_n=\{a,b\}^{n-1}a\{a,b\}^*</math>.
Ce langage est reconnu par un automate à <math>n+1</math> états plus un état puits, mais son transposé, une fois déterminisé, requiert <math>2^n</math> états<ref name="BBCF"/>{{,}}<ref>D'autres exemples sont donnés dans divers manuels, et aussi, parmi les plus anciens, dans {{harvsp|Leiss|1981}} pour un alphabet ternaire où <math>2^n</math> états sont requis pour un automate de départ de n états.</ref>.

Il a été observé<ref name="BBCF"/> que dans la pratique l'algorithme donne des résultats meilleurs que l'on pourrait penser. Ceci pose la question de la [[complexité en moyenne]] de l’algorithme. Un article de De Felice et Nicaud<ref>{{harvsp|De Felice|Nicaud|2013}}.</ref> apporte une réponse à cette question : l'algorithme de Brzozowski est ''génériquement super-polynomial''. Ce terme technique signifie la complexité en moyenne, et même que la [[complexité générique]] de l'algorithme est plus grande que tout polynôme. Le terme « complexité générique » signifie que l'on est autorisé à « ignorer », dans le calcul de la moyenne, un ensemble de cas particulièrement désavantageux, sous réserve que cet ensemble de cas soit de taille négligeable en un sens que l'on peut préciser.

== Algorithmes de raffinements de partitions ==
=== Principe ===
Les algorithmes de Moore et de Hopcroft sont des algorithmes de raffinements de [[partition (mathématiques)|partitions]]. On commence, dans les deux algorithmes, avec une hypothèse naïve, en supposant que l'automate minimal n'a que deux états et, en examinant la fonction de transition, on raffine la partition initiale tant que c'est nécessaire. Le raffinement consiste à trouver des états séparables au sens défini ci-dessus : deux états <math>p</math> et <math>q</math> sont ''séparables'' 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.

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.

=== Algorithme de Moore ===
{{article détaillé|Algorithme de Moore de minimisation d'un automate fini}}
L'''algorithme de Moore'' pour la minimisation d'automates est dû à {{harvsp|Moore|1956}}. L'algorithme maintient une partition des états, constituée initialement de deux classes, formées des états terminaux et des autres. La partition est ensuite raffinée jusqu'à obtenir une partition stable. À chaque étape, on remplace la partition courante par la partition qui est l'intersection de la partition courante et des partitions induites par les préimages des classes par les lettres de l'alphabet. L'algorithme s'arrête lorsque ce remplacement ne modifie pas la partition courante. On montre que les classes de la partition finale sont constituées d'états inséparables, et forment donc les états de l'automate minimal.

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

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

On considère les équivalences <math>\sim_0, \sim_1, \ldots</math> sur l’ensemble des états 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>.
Chaque ensemble <math>L_p^{(h)}</math> est donc 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. Cela signifie que l'on peut pas les séparer par des mots de longueur au plus <math>h</math>.
Les équivalences <math>\sim_h</math> sont parfois appelées ''équivalences de Moore'' d'ordre <math>h</math><ref name="BBCF"/>. Ces équivalences se calculent facilement grâce à la propriété suivante :
{{théorème|Lemme|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 \text{  et  }  p\cdot a\sim_hq\cdot a \text{  pour toute lettre  } 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>. Plus précisément, on détermine, pour toute lettre <math>a\in A</math>, 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.

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 [[Groupe des classes d'idéaux|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.

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"/>.

=== Algorithme de Hopcroft ===
{{Article détaillé|Algorithme de Hopcroft de minimisation d'un automate fini}}
L'algorithme, appelé ainsi d'après son inventeur, est dû à [[John Hopcroft]]<ref name="Hopcroft">{{harvsp|Hopcroft|1971}}.</ref> et il a été présenté en 1971; il opère par raffinement successif d'une partition initialement grossière de l'ensemble des états de l'automate déterministe fini à minimiser.

==== Principe ====

L'algorithme débute avec la partition la plus grossière, dont les deux classes sont composées des états terminaux et des autres. La partition est progressivement raffinée en un nombre croissant de classes plus petites. Chaque tour de l'algorithme partage des ensembles d'états en deux parties plus petites.

L'opération de base est la '''coupure''' (« splitting » en anglais)<ref>Le terme ''coupure'' est employé par {{harvsp|Carton|2008|p=49}}.</ref>. Un ensemble d'états <math>X</math> est ''coupé'' par la paire <math>(Z,a)</math> formée d'un ensemble <math>Z</math> et d'une lettre <math>a</math> si les ensembles

:<math>X'=\{q\in X \mid q\cdot a \in Z\}</math> et <math>X'' = \{q\in X \mid q\cdot a \notin Z\}</math>

sont tous les deux non vides. Dans le cas contraire, on dit que <math>X</math> est ''stable'' pour <math>(Z,a)</math>.

L'algorithme maintient un ensemble <math>\mathcal{W}</math> de couples <math>(Z,a)</math>, candidats à couper des éléments de la partition en cours; cet ''ensemble de candidats en attente'' est appelé le « ''waiting set'' » en anglais.

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

<syntaxhighlight lang="ocaml">
P := {F, Q \ F};                                             "Partition initiale"
W := l'ensemble vide;                                        "Candidats en attente"
for each a in A do
     ajouter (min(F, Q\F),a) à W;                            "Initialisation de l'ensemble W"
while (W ≠ l'ensemble vide) do
     choisir ensemble (Z,a) dans W et l'enlever de W
     for each X de P coupé par (Z,a) en X' et X'' do         "Calcul de la coupe"
          remplacer X in P par les deux ensembles X' et X''  "Raffinement de la partition"
          for each b in A do                                 "Mise-à-jour de l'ensemble" 
               if (X,b) est in W                             "des candidats en attente"
                    remplacer (X,b) in W par (X',b) et (X'',b)
               else
                    ajouter le plus petit de (X',b) et (X'',b) à W;
          end;
     end;
end;
</syntaxhighlight>

Le but de l'algorithme est d'obtenir par coupes successives un automate déterministe minimal. L'algorithme procède en testant la stabilité de chaque groupe d'états de la partition <math>P</math> par toutes les coupes possibles.

L'algorithme débute avec la partition <math>P</math> composée de l'ensemble des états terminaux <math>T</math> et de l'ensemble des états non terminaux <math>Q\setminus T</math>. <math>\mathcal{W}</math> est l'ensemble des ''candidats en attente'' pour raffiner la partition <math>P</math>. On ajoute à <math>\mathcal{W}</math> tout couple de la forme <math>(S, a)</math>, avec <math>a</math> une lettre et <math>S</math> le plus petit des ensembles <math>T</math> et <math>Q\setminus T</math>.

L'algorithme choisit itérativement un ensemble <math>(Z,a)</math> dans l'ensemble des ''candidats en attente'' <math>\mathcal{W}</math>, le retire de l'ensemble et, pour chaque partie <math>X</math> de la partition courante, il teste si <math>X</math> est coupé par <math>(Z,a)</math>.
Dans l’affirmative, la partition est mise à jour en remplaçant <math>X</math> par les deux parties <math>X'</math> et <math>X''</math> résultant de la coupure. De plus, l'ensemble des candidats en attente est augmenté, pour toute lettre <math>b</math>, de <math>(X',b)</math> et <math>(X'',b)</math> ou du plus petit de <math>(X',b)</math> et <math>(X'',b)</math>, selon que <math>(X,b)</math> est dans ce ''waiting set'' ou non.

A chaque [[itération]], soit l'ensemble <math>\mathcal{W}</math> perd un élément, soit la partition est raffinée. Comme la partition ne peut être raffinée indéfiniment parce que l'automate est fini, le nombre d'itérations est donc fini. Ceci prouve donc la terminaison de l'algorithme.

==== Complexité et optimalité ====

La [[complexité en temps]] de l’algorithme de Hopcroft, dans le pire des cas, est <math>O(s\cdot n\log n)</math> où <math>n</math> est le nombre d'états de l'automate et <math>s</math> est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des <math>sn</math> transitions de l'automate, les ensembles retirés du ''waiting set'' qui contiennent l'état d'arrivé d'une transition ont une taille diminuée de moitié au moins à chaque fois, donc chaque transition participe à au plus <math>O(\log n)</math> étapes de coupure dans l'algorithme.

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010<ref name="BBCF"/>. L'algorithme initial demande que l'automate de départ soit déterministe et complet. On peut adapter l'algorithme au cas des automates déterministes finis incomplets<ref>{{Article|prénom=Anti|nom=Valmari
|titre=Fast brief practical DFA minimization|journal=Information Processing Letters|volume=112|numéro=6|mois=mars|année=2012|passage=213-217|doi=10.1016/j.ipl.2011.12.004}}.</ref>. L'implémentation est en temps <math>O(n+m\cdot \log m)</math>, où <math>m</math> est le nombre de transitions de l'automate. On a toujours <math>m\le sn</math>.

Il reste un certain degré de liberté dans le choix du candidat que l'on retire de l'ensemble <math>\mathcal{W}</math> des candidats en attente. Cela dépend aussi du choix de la [[Structure de données|structure de donnée]] choisie : l'ensemble peut être par exemple organisé en pile (structure LIFO) ou en file (structure FIFO). Il a été prouvé qu'un choix approprié de la stratégie permet à l'algorithme de Hopcroft d'être toujours meilleur que l'algorithme de Moore<ref name="BBCF"/>. En particulier, l'algorithme a une [[complexité en moyenne]] en <math>O(sn\log \log n)</math>.

== Minimisation d'automates non déterministes ==

Les algorithmes décrits ci-dessus ne s'appliquent pas à des automates non déterministes. Alors que la notion d'automate minimal, compris comme automate ayant un nombre minimal d'états, a parfaitement un sens dans le cas des automates non déterministes, l'unicité n'est plus assurée, et le problème général est [[PSPACE-complet]] au sens de la [[Théorie de la complexité (informatique théorique)|théorie de la complexité]]<ref>{{harvsp|Hopcroft|Motwani|Ullman|2007|id=HopcroftEtAl2007|loc=Section 4.4, {{p.|163}}, Encadré intitulé ''Minimizing the States of an NFA''}}.</ref>{{,}}<ref>{{Lien web|url=http://www.theoinf.uni-bayreuth.de/download/The_Tractability_Frontier_for_NFA_Minimization_Talk.pdf|titre=The Tractability Frontier for NFA Minimization
|série=Colloquium Theoretische Informatik Universität Bayreuth|auteur=Henrik Björklund et Wim Martens
|jour=4|mois=juin|année=2008|consulté le=1 décembre 2014
}}.</ref>.

== Notes et références ==
{{Traduction/Référence|en|DFA minimization|630958603|type=note}}
{{Références}}

== Bibliographie ==
; Articles historiques
<!-- Brzoz -->
* {{chapitre
 | auteur=Janusz Brzozowski
 | titre chapitre= Canonical regular expressions and minimal state graphs for definite events
 | mr = 0175719
 | passage = 529–561
 | éditeur = Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y.
 | titre ouvrage= Proc. Sympos. Math. Theory of Automata (New York, 1962)
 | année = 1963}}.
<!-- Moore -->
* {{chapitre
 | nom = Moore | prénom = Edward F. | lien auteur = Edward F. Moore
 | titre chapitre = Gedanken-experiments on sequential machines
 | mr = 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}}.
<!-- Hopcroft -->
* {{chapitre
 | nom = Hopcroft | prénom = John | lien auteur = John Hopcroft
 | titre chapitre = An {{math|''n'' log ''n''}} algorithm for minimizing states in a finite automaton
 | mr = 0403320
 | lieu = New York
 | passage = 189–196
 | éditeur = Academic Press
 | titre ouvrage= Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971)
 | année = 1971}}

; Manuels

<!-- AHU -->
* {{Ouvrage| prénom1=Alfred V.| nom1=Aho| lien auteur1=Alfred Aho| prénom2=John E.| nom2=Hopcroft| lien auteur2=John Hopcroft| prénom3=Jeffrey D.| nom3=Ullman| lien auteur3=Jeffrey D. Ullman| titre=The Design and Analysis of Computer Algorithms| éditeur=[[Addison-Wesley]]| année=1974| passage=157–162 (Chapitre 4.13 Partitioning)| isbn=}}.
<!-- BBCF -->
* {{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 }}
<!-- Carton -->
* {{Langages formels, calculabilité et complexité}}
<!-- HUM -->
* {{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=2-7117-4807-3 | zbl=1188.68177}}
* {{Ouvrage| 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}}
* {{Ouvrage | auteur1=Peter Linz | titre=An Introduction to Formal Languages and Automata | lieu=Sudbury, MA | éditeur=Jones & Bartlett Publishers | année=2011 | numéro d'édition=5 | pages totales=437 | isbn=978-1-4496-1552-9 | lire en ligne=https://books.google.com/books?id=hsxDiWvVdBcC&printsec=frontcover}}.
; Autres références
* {{chapitre
 | nom1 = Câmpeanu | prénom1 = Cezar
 | nom2 = Culik II| prénom2 = Karel
 | nom3 = Salomaa | prénom3 = Kai
 | nom4 = Yu | prénom4 = Sheng
 | titre chapitre = State Complexity of Basic Operations on Finite Languages
 | doi = 10.1007/3-540-45526-4_6
 | passage = 60–70
 | éditeur = Springer-Verlag
 | collection = Lecture Notes in Computer Science
 | titre ouvrage = 4th International Workshop on Automata Implementation (WIA '99)
 | numéro dans collection = 2214
 | année = 2001}}.
* {{article
 | nom = Leiss | prénom = Ernst
 | doi = 10.1016/S0304-3975(81)80005-9
 | math reviews = 603263
 | numéro = 3
 | journal = Theoretical Computer Science
 | passage = 323–330
 | titre = Succinct representation of regular languages by Boolean automata
 | volume = 13
 | année = 1981}}.
* {{chapitre|auteur1= Sven De Felice|auteur2=Cyril Nicaud
 |titre chapitre=Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
 |titre ouvrage=Developments in Language Theory - 17th International Conference|année=2013
 |passage=179-190|doi=10.1007/978-3-642-38771-5_17
 |auteurs ouvrage= Marie-Pierre Béal et Olivier Carton (éditeurs)
 |éditeur= Springer-Verlag
 |collection=Lecture Notes in Computer Science
 |numéro dans collection = 7907
 |isbn      = 978-3-642-38770-8}}
* {{article
 | nom1 = Kameda | prénom1 = Tsunehiko
 | nom2 = Weiner | prénom2 = Peter
 | doi = 10.1109/T-C.1970.222994
 | numéro = 7
 | journal = IEEE Transactions on Computers
 | titre = On the state minimization of nondeterministic finite automata
 | volume = 100
 | année = 1970}}.
* {{article
 | nom = Knuutila | prénom = Timo
 | doi = 10.1016/S0304-3975(99)00150-4
 | numéro = 1-2
 | journal = Theoretical Computer Science
 | math reviews  = 1795249
 | pages = 333–363
 | titre = Re-describing an algorithm by Hopcroft
 | volume = 250
 | année = 2001}}.
* {{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}}.
* {{article|langue=en|nom1=Gries|prénom1=David
 |titre=Describing an algorithm by Hopcroft
 |journal=Acta Informatica|volume=2|numéro=2|année=1973|pages=97-109
 |doi=10.1007/BF00264025}}.



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

{{DEFAULTSORT:Automate minimal}}
[[Catégorie:Automates finis et langages réguliers]]
[[Catégorie:Théorie des automates]]