Minimisation d'un automate fini déterministe

Dans cet automate, ltous les états sont accessible, les états c, d et e sont indistinguables, ainsi que les états a et b.

Automate minimal équivalent. Les états indistinguables sont regroupés en états.

In automata theory (a branch of computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equivalent if they recognize the same regular language. Several different algorithms accomplishing this task are known and described in standard textbooks on automata theory.

En Informatique, 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 peut procurer. Il est souvent notable dans le cas de dictionnaires, ou d'autres ensembles finis de données. 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.

Les algorithmes généraux les plus connus - nommés d'après leur inventeurs - sont l'algorithme de Brzozowski, l'algorithme de Moore, et l'algorithme de Hopcroft. D'autres algorithmes spécifiques existent, par exemple pour la minimisation d'automates reconnaissant des ensembles finis de mots, comme l'algorithme de Revuz 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 transducteurs finis. Il n'existe pas de procédé analogue pour la minimisation d'automates plus généraux, comme les automates à pile ou les automates linéairement bornés. où l'équivalence, c'est-à-dire la question de savoir si deux automates reconnaissent le même langage, est indécidable.

Une application importante de la minimisation des automates finis déterministes est qu'elle permet de tester si deux automates finis donnés sont équivalents, c'est-à-dire reconnaissent le même langage. Ceci résulte du fait que l'automate fini minimal reconnaissant un langage est unique, à 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. 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 existe 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.

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. 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 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 é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

${\mathcal {A}}=(Q,i,T)$

sur un alphabet $A$. Ici $Q$ est l'ensemble des états, $i$ est l'état initial, $T$ est l'ensemble des états terminaux. La fonction de transition est notée par un simple point. Un état $q$ est est accessible s'il existe un mot $w$ tel que $q=i\cdot w$, 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é de l'algorithme est linéaire en fonction du produit $\operatorname {Card} (Q)\times \operatorname {Card} (A)$ du nombre d'états par la taille de l'alphabet. Le code suivant en est une réalisation :

Calcul des états accessibles

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;

 

Les états inaccessibles peuvent être supprimés sans modifier le langage reconnu par l'automate.

États indistinguables

Soit

${\mathcal {A}}=(Q,i,T)$

un automate déterministe complet. Deux états $p$ et $q$ sont indistinguables ou inséparables si tout mot $w$ reconnu par ${\mathcal {A}}$ à partir de $p$ est aussi reconnu à partir de $q$ et réciproquement, formellement si pour tout mot $w$ :

$p\cdot w\in T\iff q\cdot w\in T$.

Deux états sont séparables s'ils ne sont pas inséparables. Un critère de minimalité utile est le suivant :

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) : le langage à droite d'un état $q$ est par définition le langage

$L_{q}({\mathcal {A}})=\{w\in A^{*}\mid q\cdot w\in T\}$.

C'est donc l'ensemble des mots reconnus par l’automate en prenant $q$ comme état initial. Alors deux états sont inséparables si et seulement s'il ont même langage à droite.

Algorithme de Brzozowski

Brzozowski présente, dans son article de 1963, un algorithme de minimisation qui est basé sur la déterminisation d'un automate fini non nécessairement déterministe. Cet algorithme, conceptuellement simple, produit - de façon étonnante - un automate minimal.

L'automate transposé d'un automate fini (non déterministe)

${\mathcal {A}}=(Q,{\mathcal {F}},I,T)$

où $I$ et $T$ sont les états initiaux et terminaux et où ${\mathcal {F}}$ est l'ensemble des transitions, est l'automate obtenu en inverser le sens des transitions, et à échanger les états initiaux avec les états terminaux. Formellement, c'est l'automate${\mathcal {A}}^{R}$.</ref>

${\mathcal {A}}^{R}=(Q,{\mathcal {F}}^{R},T,I)$,

où ${\mathcal {F}}^{R}=\{(p,a,q)\mid (q,a,p)\in {\mathcal {F}}\}$. Le langage reconnu par l'automate transposé est formé des images miroir des mots reconnus par l’automate de départ. Sauf dans des cas très exceptionnels, l'automate transposé n'est pas déterministe, mais la déterminisation de l'automate donne un automate déterministe minimal. L'énoncé précis est le suivant :

Proposition (Brzozowski) —  Soit ${\mathcal {A}}$ un automate fini déterministe, et soit ${\mathcal {A}}^{\sim }$ l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé ${\mathcal {A}}^{R}$ par déterminisation et élimination des états inaccessibles. Alors l'automate ${\mathcal {A}}^{\sim }$ est minimal et reconnaît le langage miroir du langage reconnu par ${\mathcal {A}}$.

L'algorithme de minimisation d'un automate fini ${\mathcal {A}}$ est donc le suivant :

1. Calculer ${\mathcal {A}}^{\sim }$, en transposant l'automate puis en le déterminisant par la procédure usuelle par exemple qui ne conserve que les états accessibles;
2. Répéter l'opération sur l'automate obtenu : calculer $({\mathcal {A}}^{\sim })^{\sim }$ en transposant ${\mathcal {A}}^{\sim }$ puis en le déterminisant de la même manière.

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 ${\mathcal {A}}^{\sim }$ peut être exponentiel. Un exemple est fourni par le langage $K_{n}$ formé de mots de longueur au moins $n$ sur un alphabet à deux lettres $a$ et $b$, et dont la $n$-ième lettre toujours un $a$, en d'autres termes :

$K_{n}=\{a,b\}^{n-1}a\{a,b\}^{*}$.

Ce langage est reconnu par un automate à $n+1$ états plus un état puits, mais son transposé, une fois déterminisé, requiert $2^{n}$ états.

Il a été observé 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 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.

Algorithme de Moore

Les algorithmes de Moore et de Hopcroft sont des algorithmes de raffinements de 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 jusqu'à ne plus devoir continuer. Le raffinement consiste à trouver des états séparables au sens défini ci-dessus : deux états $p$ et $q$ sont séparables s'il existe un mot $w$ tel que l'état $p\cdot w$ est final et $q\cdot w$ 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 classe de la partition, et comme transitions les transitions induites sur les classes par les transitions de l'automate de départ.

L'algorithme de Moore pour la minimisation d'automates est dû à 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. A 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.

On considère plus précisément des équivalences $\sim _{0},\sim _{1},\ldots$ sur l’ensemble des états définies par

$p\sim _{h}q\iff L_{q}^{(h)}({\mathcal {A}})=L_{p}^{(h)}({\mathcal {A}})$,

où

$L_{p}^{(h)}({\mathcal {A}})=\{w\in A^{*}\mid p\cdot w\in T{\text{et }}|w|\leq h\}$.

Chaque ensemble $L_{p}^{(h)}$ est donc composé des mot de longueur au plus $h$ qui mènent de l'état $p$ à un état terminal de l’automate. Deux états sont équivalents pour la relation $\sim _{h}$ si le mêmes mots de longueur au plus $h$ mènent à des états terminaux. Cela signifie que l'on peut pas les séparer par des mots de longueur au plus $h$. Les équivalences $\sim _{h}$ sont parfois appelées équivalences de Moore d'ordre $h$. Ces équivalences se calculent facilement grâce à la propriété suivante :

Lemme — Pour deux états $p$ et $q$ et $h\geq 0$, on a

$p\sim _{h+1}q\iff p\sim _{h}q{\text{ et }}p\cdot a\sim _{h}q\cdot a{\text{ pour toute lettre }}a\in A$.

Ainsi, pour calculer l'équivalence $\sim _{h+1}$, on détermine les états qui, par une lettre, arrivent dans des classes distinctes de $\sim _{h}$ : ceux-ci sont dans des classes distinctes de $\sim _{h+1}$. Plus précisément, on détermine, pour toute lettre $a\in A$, la partition dont les classes sont constituées d'états qui, par la lettre $a$, donnent des états équivalents pour $\sim _{h}$. On forme ensuite l'intersection de ces partitions avec la partition $\sim _{h}$ elle-même.

Il est facile de vérifier que si $\sim _{k}$ et $\sim _{k+1}$ sont égales pour un entier $k$, alors $\sim _{k}$ et $\sim _{k+r}$ sont égales pour tout $r$, 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, $O(sn^{2})$, où $s$ est la taille de l'alphabet et où $n$ est le nombre d'états de l'automate. Chacune des étapes du raffinement peut être effectuée en temps $O(sn)$ 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 $n-2$ étapes suffisent. En fait, la complexité est même en $O(\ell sn)$, où $\ell$ est le nombre d'étapes de l'algorithme. On peut observer 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 $O(n\log n)$, et même en $O(n\log \log n)$, selon le choix du modèle retenu pour la distribution aléatoire.

Algorithme de Hopcroft

L'algorithme, appelé ainsi d'après son inventeur, est dû à John Hopcroft et il a été présenté en 1971; 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 le plus petit de (F,a) et (Q \ F) à 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;

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

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

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

L'algorithme maintient un ensemble ${\mathcal {W}}$ de couples $(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.

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

Lemme — Soient $X$ et $Z=Z'\cup Z''$ deux ensembles d'états, avec $Z'$ et $Z''$ disjoints non vides, et soit $a$ une lettre.

• Si $X$ est stable pour $(Z,a)$ et pour $(Z',a)$, alors $X$ est stable pour $(Z'',a)$.
• Si $X$ est stable pour $(Z',a)$ et pour $(Z'',a)$, alors $X$ est stable pour $(Z,a)$.

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

La complexité en temps de l’algorithme de Hopcroft, dans le pire des cas, est $O(sn\log n)$ où $n$ est le nombre d'états de l'automate et $s$ est la taille de l'alphabet. La borne est conséquence du fait que, pour chacune des $sn$ transitions de l'automate, les ensembles retirés du waiting set qui contiennent l'état d'arrivé d'une transition sont de taille divisé par deux au moins moitié à chaque fois, donc chaque transition participe à au plus $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.

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010. L'algorithme initial demande que l'automate de départ sont déterministe et complet. Une extension au cas des automates incomplets a aussi été décrite. L'implémentation est en temps $O(n+m\log m)$, où $m$ est le nombre de transitions de l'automate. On a toujours $m\leq sn$

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 organié en pile (structure LIFO) ou en file (structure FIFO). Des expériences pratiques on conclu à une meilleure efficacité de la représentation par pile plutôt que par file, et cet avantage a été démontré. Il a aussi été prouvé qu'un choix approprié de la stratégie permet à l'algorithme de Hopcroft d'être toujours meilleur que l'algorithme de Moore. En particulier, l'algorithme a une complexité en moyenne en $O(sn\log \log n)$.

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 sent de la théorie de la complexité.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « DFA minimization » (voir la liste des auteurs).

Bibliographie

Articles historiques

• Janusz Brzozowski, « Canonical regular expressions and minimal state graphs for definite events », dans Proc. Sympos. Math. Theory of Automata (New York, 1962), Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963 (MR 0175719), p. 529–561.
• Edward F. Moore, « Gedanken-experiments on sequential machines », dans Automata studies, Princeton, N. J., Princeton University Press, coll. « Annals of mathematics studies » (n^o 34), 1956 (MR 0078059), p. 129–153.
• 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

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).
• 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)
• 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)
• Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003 (ISBN 2-7117-4807-3, zbMATH 1188.68177)
• Patrice Séébold, Théorie des automates: Méthodes et exercices corrigés, Vuibert, 1999, 198 p. (ISBN 978-2711786305)

Autres références

• Ernst Leiss, « Succinct representation of regular languages by Boolean automata », Theoretical Computer Science, vol. 13, n^o 3,‎ 1981, p. 323–330 (DOI 10.1016/S0304-3975(81)80005-9, MR 603263).
• Sven De Felice et Cyril Nicaud, « Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata », dans Marie-Pierre Béal et Olivier Carton (éditeurs), Developments in Language Theory - 17th International Conference, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 7907), 2013 (ISBN 978-3-642-38770-8, DOI 10.1007/978-3-642-38771-5_17), p. 179-190