Algorithme de Hopcroft de minimisation d'un automate fini

En informatique théorique, et notamment en théorie des automates finis, l'algorithme de Hopcroft de minimisation d'un automate fini, appelé ainsi d'après son inventeur John Hopcroft, est un algorithme calculant l’automate déterministe fini minimal, à partir d'un automate fini donné. Cet algorithme est — en 2010 — l'algorithme le plus efficace connu. Il opère en temps ${\displaystyle O(s\cdot n\log n)}$ pour un automate à ${\displaystyle n}$ états sur un alphabet de ${\displaystyle s}$ lettres.

Description de l'algorithme

L'algorithme est dû à John Hopcroft^[1] et il a été présenté en 1971 ; il opère par raffinements successifs d'une partition initialement grossière de l'ensemble des états de l'automate déterministe fini à minimiser.

L'algorithme s'inscrit donc dans la famille des algorithmes de minimisation par raffinements successifs qui contient notamment l'algorithme de Moore de minimisation d'un automate fini ; il s'oppose aux algorithmes d'une autre nature comme l’algorithme de Brzozowski de minimisation d'un automate fini.

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)^[2]. Un ensemble d'états ${\displaystyle X}$ est coupé par la paire ${\displaystyle (Z,a)}$ formée d'un ensemble ${\displaystyle Z}$ et d'une lettre ${\displaystyle a}$ si les ensembles

${\displaystyle X'=\{q\in X\mid q\cdot a\in Z\}}$ et ${\displaystyle X''=\{q\in X\mid q\cdot a\notin Z\}}$

sont tous les deux non vides. Dans le cas contraire, on dit que ${\displaystyle X}$ est stable pour ${\displaystyle (Z,a)}$.

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

Pseudo-code

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

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;

Description formelle

Le lemme suivant^[3] est facile à prouver, mais il est à la base du mécanisme de mise-à-jour du waiting set dans l'algorithme :

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 ${\displaystyle P}$ par toutes les coupes possibles.

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

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

À chaque itération, soit l'ensemble ${\displaystyle {\mathcal {W}}}$ 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 ${\displaystyle O(s\cdot n\log n)}$ où ${\displaystyle n}$ est le nombre d'états de l'automate et ${\displaystyle s}$ est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des ${\displaystyle sn}$ 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 ${\displaystyle O(\log n)}$ étapes de coupure dans l'algorithme. Une structure de données appropriée permet de réaliser le raffinement d'une partition par une coupure en un temps proportionnel au nombre de transitions qui y sont impliquées^[1],[4].

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010^[5]. 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^[6]. L'implémentation est en temps ${\displaystyle O(n+m\cdot \log m)}$, où ${\displaystyle m}$ est le nombre de transitions de l'automate. On a toujours ${\displaystyle m\leq sn}$.

Il reste un certain degré de liberté dans le choix du candidat que l'on retire de l'ensemble ${\displaystyle {\mathcal {W}}}$ des candidats en attente. Cela dépend aussi du choix de la structure de donnée choisie : l'ensemble peut être par exemple organisé en pile (structure LIFO) ou en file (structure FIFO). Des expériences pratiques ont conclu à une meilleure efficacité de la représentation par pile plutôt que par file, et cet avantage a été démontré. 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^[5],[7]. En particulier, l'algorithme a une complexité en moyenne en ${\displaystyle O(sn\log \log n)}$.

Notes et références

Articles connexes

• Algorithme de Moore de minimisation d'un automate fini
• Algorithme de Brzozowski de minimisation d'un automate fini

Bibliographie

Article original

• John Hopcroft, « An n log n algorithm for minimizing states in a finite automaton », dans Theory of machines and computations (Proc. Internat. Sympos., Technion, Haifa, 1971), New York, Academic Press, 1971 (MR 0403320), p. 189–196. — Version préliminaire Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, janvier 1971.

Manuels

• Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974, p. 157–162 (Chapitre 4.13 Partitioning).
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [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, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Jean Berstel, Luc Boasson, Olivier Carton et Isabelle Fagnot, « Minimization of Automata », dans Automata: from Mathematics to Applications, European Mathematical Society, 2010 (arXiv 1010.5318)

Articles

• (en) Julien David, « Average complexity of Moore’s and Hopcroft’s algorithms », Theoretical Computer Science, vol. 417,‎ 2012, p. 50–65 (DOI 10.1016/j.tcs.2011.10.011).
• (en) Andrei Păun, Mihaela Păun et Alfonso Rodríguez-Patón, « On the Hopcroft’s minimization technique for DFA and DFCA », Theoretical Computer Science, vol. 410, n^os 24-25,‎ 2009, p. 2424–2430 (DOI 10.1016/j.tcs.2009.02.034).
• Manuel Baclet et Claire Pagetti, « Around Hopcroft’s Algorithm », dans International Conference on Implementation and Application of Automata, coll. « Lecture Notes in Computer Science » (n^o 4094), 2006, 114–125 p. (DOI 10.1007/11812128_12).
• (en) David Gries, « Describing an algorithm by Hopcroft », Acta Informatica, vol. 2, n^o 2,‎ 1973, p. 97-109 (DOI 10.1007/BF00264025).
• *Timo Knuutila, « Re-describing an algorithm by Hopcroft », Theoretical Computer Science, vol. 250, n^os 1-2,‎ 2001, p. 333–363 (DOI 10.1016/S0304-3975(99)00150-4, MR 1795249).

• Portail de l'informatique théorique