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. 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, sont des livres standards en français, contient des exercices détaillés ; est une référence anglaise..
Les algorithmes généraux les plus connus - nommés d'après leurs 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.
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, Section 4.4.3, "Minimization of DFA's", p. 159.. 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.. 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
sur un alphabet . Ici est l'ensemble des états, est l'état initial, est l'ensemble des états terminaux. La fonction de transition est notée par un simple point. Un état est accessible s'il existe un mot tel que , 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 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;
États indistinguables
Soit
un automate déterministe complet. Deux états et sont indistinguables ou inséparables si tout mot reconnu par à partir de est aussi reconnu à partir de et réciproquement, formellement si pour tout mot : . 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) : le langage à droite d'un état est par définition le langage . C'est donc l'ensemble des mots reconnus par l’automate en prenant 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 , sur l'ensemble des états définie par . 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.
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 Hopcroft, Motwani et Ullman et celui de Peter Linz..
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 d'états distincts comme suit : Pour toute paire d'états, si est final et ne l'est pas ou vice-versa, marquer comme séparables. Répéter l'opération suivante tant qu'une nouvelle paire a été marquée : Pour toute paire et toute lettre , calculer et . Si la paire est marquée comme étant séparable, marquer comme séparable. Méthode de remplissage de table Hopcroft et. al.. appellent (« 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 : vignette|upright=1.5|Exemple pour le remplissage de table. Les états terminaux sont en rose. ABCDEFGHBxCxxDxxxExxxFxxxxGxxxxxHxxxxxx 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
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.
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 :
L'algorithme de minimisation d'un automate fini est alors le suivant : Calculer , 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 en transposant 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 peut être exponentiel. Un exemple est fourni par le langage formé de mots de longueur au moins sur un alphabet à deux lettres et , et dont la -ième lettre toujours un , en d'autres termes : . Ce langage est reconnu par un automate à états plus un état puits, mais son transposé, une fois déterminisé, requiert étatsD'autres exemples sont donnés dans divers manuels, et aussi, parmi les plus anciens, dans pour un alphabet ternaire où états sont requis pour un automate de départ de 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.
Algorithmes de raffinements de partitions Principe 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 et sont séparables s'il existe un mot tel que l'état est final et 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