Algorithme de Brzozowski de minimisation d'un automate fini

Article principal : Minimisation d'un automate fini déterministe.

En théorie des automates, et notamment des automates finis déterministes, l'algorithme de Brzozowski de minimisation d'un automate fini, publié par Janusz A. Brzozowski en 1963^[1], est un algorithme de minimisation d'un automate fini fondé sur une double transposition et une double déterminisation.

L'algorithme est, avec l'algorithme de Moore et l'algorithme de Hopcroft, l'un des trois algorithmes principaux de minimisation d'un automate fini déterministe. Ce n'est pas le plus efficace, mais il est plus simple à expliquer. Il est remarquable que la minimisation se ramène ainsi à deux opérations conceptuellement très différentes : la transposition et la déterminisation.

Prérequis

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

Automate transposé

L'automate transposé de ${\mathcal {A}}$ , noté $tr({\mathcal {A}})$ , est l'automate obtenu en inversant le sens des transitions, et en échangeant les états initiaux avec les états terminaux. Formellement, c'est l'automate défini par

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

,

où ${\mathcal {F}}^{R}=\{(p,a,q)\mid (q,a,p)\in {\mathcal {F}}\}$ .

Automate déterminisé

L'automate déterminisé de ${\mathcal {A}}$ , noté $\det({\mathcal {A}})$ ^[2], est l'automate déterministe, dont tous les états sont accessibles, équivalent à l'automate de départ ${\mathcal {A}}$ , obtenu par la procédure usuelle de construction par sous-ensembles.

Algorithme

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

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

.

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

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

Calculer $\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 ;
Répéter l'opération 1 sur l'automate $\det(\operatorname {\,tr\,} ({\mathcal {A}}))$ obtenu.

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

Complexité

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. 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 $O(|{\mathcal {A}}|+|\operatorname {det} ({\mathcal {A}})|)$ , l’automate intermédiaire $\operatorname {\,tr} (\det(\operatorname {\,tr} (A)))$ est de taille $O(2^{n})$ , l’automate final aussi, d’où une complexité totale en $O(2^{n})$ . Un exemple où la borne est atteinte est fourni par le langage $K_{n}$ des mots de longueur au moins $n$ sur un alphabet à deux lettres $a$ et $b$ , et dont la $n$ -ième lettre est 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^[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.

Justification

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

Proposition (Brzozowski) — Soit ${\mathcal {A}}$ un automate fini déterministe accessible, et soit ${\mathcal {A}}^{\sim }=\det(\operatorname {\,tr} ({\mathcal {A}}))$ l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé 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}}$ .

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

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

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

Notes et références

↑ Brzozowski 1963.
↑ Comme dans : Benjamin Monmège et Sylvain Schmitz, « Notes de révision : : Automates et langages », Préparation à l’agrégation de mathématiques 2011–2012, sur Préparation en langages formels, LSV, ENS Cachan & CNRS (consulté le 8 juillet 2016).
↑ ^{a et b} Berstel et al. 2010.
↑ De Felice et Nicaud 2013.
↑ Felice et Nicaud 2016.

Bibliographie

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)

Portail de l'informatique théorique

[1] Brzozowski 1963.

[2] Comme dans : Benjamin Monmège et Sylvain Schmitz, « Notes de révision : : Automates et langages », Préparation à l’agrégation de mathématiques 2011–2012, sur Préparation en langages formels, LSV, ENS Cachan & CNRS (consulté le 8 juillet 2016).

[BBCF-3] {a et b} Berstel et al. 2010.

[4] De Felice et Nicaud 2013.

[FeliceNicaud2016-5] Felice et Nicaud 2016.

[1]

[2]

[3]

[4]

[5]