Algorithme de Brzozowski de minimisation d'un automate fini
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
[modifier | modifier le code]Soit un automate fini (déterministe ou non déterministe), où et sont les ensembles d'états respectivement initiaux et terminaux et où est l'ensemble des transitions, sur un alphabet fixé.
Automate transposé
[modifier | modifier le code]L'automate transposé de , noté , 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
- ,
où .
Automate déterminisé
[modifier | modifier le code]L'automate déterminisé de , noté [2], est l'automate déterministe, dont tous les états sont accessibles, équivalent à l'automate de départ , obtenu par la procédure usuelle de construction par sous-ensembles.
Algorithme
[modifier | modifier le code]L'algorithme de minimisation part d'un automate reconnaissant un langage (déterministe ou non) et construit l'automate
- .
L'automate est l'automate déterministe minimal reconnaissant .
L'algorithme de minimisation d'un automate fini est donc en deux étapes :
- 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 1 sur l'automate obtenu.
La première étape se fait à partir d'un automate fini quelconque, déterministe ou non, la deuxième par contre prend en argument l'automate déterministe accessible complet .
Complexité
[modifier | modifier le code]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. 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 , l’automate intermédiaire est de taille , l’automate final aussi, d’où une complexité totale en . Un exemple où la borne est atteinte est fourni par le langage des mots de longueur au moins sur un alphabet à deux lettres et , et dont la -ième lettre est 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 é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
[modifier | modifier le code]L'énoncé précis qui justifie la construction est le suivant :
Proposition (Brzozowski) — Soit un automate fini déterministe accessible, et soit l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé par déterminisation et élimination des états inaccessibles. Alors l'automate est minimal et reconnaît le langage miroir du langage reconnu par .
La démonstration n’est pas très difficile : soit le langage reconnu par l'automate déterministe complet et soit l'automate transposé reconnaissant .
Pour prouver que est minimal, on montre que si , alors dans l'automate . Ceci prouve que est isomorphe à l'automate minimal de .
Soit un état de . Comme est accessible, il existe un mot tel que dans . On a donc et aussi . Comme est déterministe, est l'unique état tel que dans . Tout chemin de vers étiqueté par passe par l'état , et donc . Ceci montre que . L'inclusion dans l’autre sens se montre de la même façon.
Notes et références
[modifier | modifier le code]- 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 ).
- Berstel et al. 2010.
- De Felice et Nicaud 2013.
- Felice et Nicaud 2016.
Bibliographie
[modifier | modifier le code]- 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, , p. 529-561 (lire en ligne)
- Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, , 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, (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 » (no 7907), (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, no 02, , p. 109–126 (DOI 10.1142/S0129054116400025)