Algorithme de Brzozowski de minimisation d'un automate fini

Soit ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$ un automate fini (déterministe ou non déterministe), où ${\displaystyle I}$ et ${\displaystyle T}$ sont les ensembles d'états respectivement initiaux et terminaux et où ${\displaystyle {\mathcal {F}}}$ est l'ensemble des transitions, sur un alphabet fixé.

L'algorithme de minimisation part d'un automate ${\displaystyle {\mathcal {A}}}$ reconnaissant un langage ${\displaystyle L}$ (déterministe ou non) et construit l'automate

${\displaystyle {\mathcal {A}}(L)=\det(\operatorname {\,tr\,} (\det(\operatorname {\,tr\,} ({\mathcal {A}}))))}$.

L'automate ${\displaystyle {\mathcal {A}}(L)}$ est l'automate déterministe minimal reconnaissant ${\displaystyle L}$.

L'algorithme de minimisation d'un automate fini ${\displaystyle {\mathcal {A}}}$ est donc en deux étapes :

1. Calculer ${\displaystyle \det(\operatorname {\,tr\,} ({\mathcal {A}}))}$, 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 1 sur l'automate ${\displaystyle \det(\operatorname {\,tr\,} ({\mathcal {A}}))}$ obtenu.

La première étape se fait à partir d'un automate fini ${\displaystyle {\mathcal {A}}}$ quelconque, déterministe ou non, la deuxième par contre prend en argument l'automate déterministe accessible complet ${\displaystyle \det(\operatorname {\,tr\,} ({\mathcal {A}}))}$.

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 ${\displaystyle {\mathcal {A}}^{\sim }}$ peut être exponentiel. On pourrait penser que la complexité est doublement exponentielle puisqu'il y a deux déterminisations consécutives, mais ce n'est pas le cas : Le coût d’une déterminisation est en ${\displaystyle O(|{\mathcal {A}}|+|\operatorname {det} ({\mathcal {A}})|)}$, l’automate intermédiaire ${\displaystyle \operatorname {\,tr} (\det(\operatorname {\,tr} (A)))}$ est de taille ${\displaystyle O(2^{n})}$, l’automate final aussi, d’où une complexité totale en ${\displaystyle O(2^{n})}$. Un exemple où la borne est atteinte est fourni par le langage ${\displaystyle K_{n}}$ des mots de longueur au moins ${\displaystyle n}$ sur un alphabet à deux lettres ${\displaystyle a}$ et ${\displaystyle b}$, et dont la ${\displaystyle n}$-ième lettre est un ${\displaystyle a}$, en d'autres termes :

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

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

Il a été observé[3] que l'algorithme semble donner des résultats meilleurs dans la pratique que l'on pourrait penser. Ceci pose la question de la complexité en moyenne de l’algorithme. Un article de De Felice et Nicaud[4] - [5] apporte une réponse à cette question : l'algorithme de Brzozowski est génériquement super-polynomial. Ce terme technique signifie que 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.

L'énoncé précis qui justifie la construction est le suivant :

La démonstration n’est pas très difficile : soit ${\displaystyle L}$ le langage reconnu par l'automate déterministe complet ${\displaystyle {\mathcal {A}}=(Q,q_{0},T)}$ et soit ${\displaystyle \operatorname {\,tr} ({\mathcal {A}})=(Q,T,q_{0},)}$ l'automate transposé reconnaissant ${\displaystyle M=L^{\sim }}$.

Pour prouver que ${\displaystyle {\mathcal {A}}^{\sim }}$ est minimal, on montre que si ${\displaystyle u^{-1}M=v^{-1}M}$, alors ${\displaystyle T\cdot u=T\cdot v}$ dans l'automate ${\displaystyle {\mathcal {A}}^{\sim }}$. Ceci prouve que ${\displaystyle {\mathcal {A}}^{\sim }}$ est isomorphe à l'automate minimal de ${\displaystyle M}$.

Soit ${\displaystyle p}$ un état de ${\displaystyle T\cdot u}$. Comme ${\displaystyle {\mathcal {A}}}$ est accessible, il existe un mot ${\displaystyle w}$ tel que ${\displaystyle p\cdot w=q_{0}}$ dans ${\displaystyle \operatorname {\,tr} ({\mathcal {A}})}$. On a donc ${\displaystyle uw\in M}$ et aussi ${\displaystyle vw\in M}$. Comme ${\displaystyle {\mathcal {A}}}$ est déterministe, ${\displaystyle p}$ est l'unique état tel que${\displaystyle p\cdot w=q_{0}}$ dans ${\displaystyle \operatorname {\,tr} ({\mathcal {A}})}$. Tout chemin de ${\displaystyle T}$ vers ${\displaystyle q_{0}}$ étiqueté par ${\displaystyle vw}$ passe par l'état ${\displaystyle p}$, et donc ${\displaystyle p\in T\cdot v}$. Ceci montre que ${\displaystyle T\cdot u\subset T\cdot v}$. L'inclusion dans l’autre sens se montre de la même façon.

• Janusz A. Brzozowski, « Canonical regular expressions and minimal state graphs for definite events », Proceedings of the Symposium on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, April 1962, New York, Wiley,‎ 1963, p. 529-561 (lire en ligne)
• Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5, BNF 38989710, zbMATH 1188.68177)
• 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)
• 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
• (en) Sven De Felice et Cyril Nicaud, « Average Case Analysis of Brzozowski's Algorithm », International Journal of Foundations of Computer Science, vol. 27, n^o 02,‎ 2016, p. 109–126 (DOI 10.1142/S0129054116400025)