Algorithme de Hopcroft de minimisation d'un automate fini

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et notamment en théorie des automates finis, l'algorithme de Hopcroft de minimisation d'un automate fini est un algorithme, appelé ainsi d'après son inventeur John Hopcroft, pour calculer 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 pour un automate à états sur un alphabet de lettres.

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

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 est coupé par la paire formée d'un ensemble et d'une lettre si les ensembles

et

sont tous les deux non vides. Dans le cas contraire, on dit que est stable pour .

L'algorithme maintient un ensemble de couples , 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[modifier | modifier le 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[modifier | modifier le code]

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

Lemme — Soient et deux ensembles d'états, avec et disjoints non vides, et soit une lettre.

  • Si est stable pour et pour , alors est stable pour .
  • Si est stable pour et pour , alors est stable pour .

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 par toutes les coupes possibles.

L'algorithme débute avec la partition composée de l'ensemble des états terminaux et de l'ensemble des états non terminaux . est l'ensemble des candidats en attente pour raffiner la partition . On ajoute à tout couple de la forme , avec une lettre et le plus petit des ensembles et .

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

À chaque itération, soit l'ensemble 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é[modifier | modifier le code]

La complexité en temps de l’algorithme de Hopcroft, dans le pire des cas, est est le nombre d'états de l'automate et est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des 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 é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 , où est le nombre de transitions de l'automate. On a toujours .

Il reste un certain degré de liberté dans le choix du candidat que l'on retire de l'ensemble 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 .

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

  1. a et b Hopcroft 1971.
  2. Le terme coupure est employé par Carton 2008, p. 49.
  3. Carton 2008, p. 49.
  4. Aho, Hopcroft et Ullman 1974
  5. a et b Berstel et al. 2010.
  6. Anti Valmari, « Fast brief practical DFA minimization », Information Processing Letters, vol. 112, no 6,‎ , p. 213-217 (DOI 10.1016/j.ipl.2011.12.004).
  7. David 2012.

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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, , p. 189–196. — Version préliminaire Technical Report STAN-CS-71-190, Stanford University, Computer Science Department, janvier 1971.
Manuels
Articles
  • (en) Julien David, « Average complexity of Moore’s and Hopcroft’s algorithms », Theoretical Computer Science, vol. 417,‎ , 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, no 24-25,‎ , 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 » (no 4094), , 114–125 p. (DOI 10.1007/11812128_12).
  • (en) David Gries, « Describing an algorithm by Hopcroft », Acta Informatica, vol. 2, no 2,‎ , p. 97-109 (DOI 10.1007/BF00264025).
  • *Timo Knuutila, « Re-describing an algorithm by Hopcroft », Theoretical Computer Science, vol. 250, no 1-2,‎ , p. 333–363 (DOI 10.1016/S0304-3975(99)00150-4, Math Reviews 1795249).