Minimisation d'un automate fini déterministe

On considère un automate fini déterministe complet

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

sur un alphabet ${\displaystyle A}$. Ici ${\displaystyle Q}$ est l'ensemble des états, ${\displaystyle i}$ est l'état initial, ${\displaystyle T}$ est l'ensemble des états terminaux. La fonction de transition est notée par un simple point. Un état ${\displaystyle q}$ est accessible s'il existe un mot ${\displaystyle w}$ tel que ${\displaystyle 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é en temps de l'algorithme est linéaire en fonction du produit ${\displaystyle \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 :

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;

Soit

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

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

${\displaystyle 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 :

Une façon plus condensée de présenter ce critère est d'introduire les langages à droite (« right languages » en anglais[2]) : le langage à droite d'un état ${\displaystyle q}$ est par définition le langage

${\displaystyle 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 ${\displaystyle q}$ 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 ${\displaystyle \sim }$, sur l'ensemble des états définie par

${\displaystyle q\sim q'\iff L_{q}({\mathcal {A}})=L_{q'}({\mathcal {A}})}$ .

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

La méthode est un algorithme de marquage. Elle consiste à chercher et marquer des paires d'états séparables. Elle procède les paires ${\displaystyle (p,q)}$ d'états distincts comme suit :

1. Pour toute paire ${\displaystyle (p,q)}$ d'états, si ${\displaystyle p}$ est final et ${\displaystyle q}$ ne l'est pas ou vice-versa, marquer ${\displaystyle (p,q)}$ comme séparables.
2. Répéter l'opération suivante tant qu'une nouvelle paire a été marquée :

Pour toute paire ${\displaystyle (p,q)}$ et toute lettre ${\displaystyle a}$, calculer ${\displaystyle p_{a}=p\cdot a}$ et ${\displaystyle q_{a}=q\cdot a}$. Si la paire ${\displaystyle (p_{a},q_{a})}$ est marquée comme étant séparable, marquer ${\displaystyle (p,q)}$ comme séparable.

Hopcroft et. al.[6] appellent « 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 :

Exemple pour le remplissage de table. Les états terminaux sont en rose.

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.

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 tant que c'est nécessaire. Le raffinement consiste à trouver des états séparables au sens défini ci-dessus : deux états ${\displaystyle p}$ et ${\displaystyle q}$ sont séparables s'il existe un mot ${\displaystyle w}$ tel que l'état ${\displaystyle p\cdot w}$ est final et ${\displaystyle 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 classes 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. À 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 ${\displaystyle \sim _{0},\sim _{1},\ldots }$ sur l’ensemble des états définies par

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

où

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

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

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

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

L'algorithme, appelé ainsi d'après son inventeur, est dû à John Hopcroft[10] 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.

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)[11]. 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.

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;

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.

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

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.

L'algorithme de Hopcroft est le plus efficace des algorithmes de minimisation connus en 2010[2]. 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[12]. 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). 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[2]. En particulier, l'algorithme a une complexité en moyenne en ${\displaystyle O(sn\log \log n)}$.