Voir la source de 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 [[Automate fini déterministe|automates finis déterministes]], l{{'}}'''algorithme de Brzozowski de minimisation d'un automate fini''', publié par [[Janusz A. Brzozowski]] en 1963<ref>{{harvsp|Brzozowski|1963}}.</ref>, est un algorithme de minimisation d'un automate fini fondé sur une double [[automate transposé|transposition]] et une double [[construction par sous-ensembles|déterminisation]].

L'algorithme est, avec l'[[Algorithme de Moore de minimisation d'un automate fini|algorithme de Moore]] et l'[[Algorithme de Hopcroft de minimisation d'un automate fini|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 <math>\mathcal{A} = (Q, \mathcal{F}, I, T)</math> un automate fini (déterministe ou non déterministe), où <math>I</math> et <math>T</math> sont les ensembles d'états respectivement initiaux et terminaux et où <math>\mathcal{F}</math> est l'ensemble des transitions, sur un alphabet fixé.

=== Automate transposé ===
L'[[automate transposé]] de <math>\mathcal{A}</math> , noté <math>tr(\mathcal A)</math>, 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
:<math>tr({\mathcal {A}}) = (Q, \mathcal{F}^R, T, I)</math>,
où <math>\mathcal{F}^R=\{(p,a,q)\mid (q,a,p)\in\mathcal{F}\}</math>. 

=== Automate déterminisé ===
L'automate déterminisé de <math>\mathcal{A}</math>, noté <math>\det(\mathcal{A})</math> <ref>Comme dans  : {{Lien web|langue=|lien auteur=|coauteurs=|titre=Notes de révision : : Automates et langages|url=http://www.lsv.ens-cachan.fr/~schmitz/teach/2012_agreg/notes-r62.pdf|série=Préparation à l’agrégation de mathématiques 2011–2012|site=Préparation en langages formels|éditeur=LSV, ENS Cachan & CNRS|jour=|mois=|année=|consulté le=8 juillet 2016|page=|id=|auteur=Benjamin Monmège et Sylvain Schmitz|citation=|en ligne le=}}.</ref>, est l'automate déterministe, dont tous les états sont accessibles, équivalent à l'automate de départ <math>\mathcal{A}</math>, obtenu par la procédure usuelle de [[construction par sous-ensembles]]. 

== Algorithme ==
L'algorithme de minimisation part d'un automate <math>\mathcal{A}</math> reconnaissant un langage <math>L</math> (déterministe ou non) et construit l'automate
:<math>\mathcal{A}(L)=\det(\operatorname{\,tr\,}(\det(\operatorname{\,tr\,}(\mathcal{A}))))</math>.
L'automate <math>\mathcal{A}(L)</math> est l'automate déterministe minimal reconnaissant <math>L</math>.

L'algorithme de minimisation d'un automate fini <math>\mathcal{A}</math> est donc en deux étapes :
# Calculer <math>\det(\operatorname{\,tr\,}(\mathcal{A}))</math>, 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 <math>\det(\operatorname{\,tr\,}(\mathcal{A}))</math> obtenu. 

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

== 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  <math>\mathcal{A}^\sim</math> 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 <math>O(|\mathcal{A}|+|\operatorname{ det}(\mathcal{A})|)</math>, l’automate intermédiaire <math>\operatorname{\,tr}(\det(\operatorname{\,tr}(A)))</math> est de taille <math>O(2^n)</math>, l’automate final aussi, d’où une complexité totale en <math>O(2^n)</math>.
Un exemple où la borne est atteinte est fourni par le langage <math>K_n</math> des mots de longueur au moins <math>n</math> sur un alphabet à deux lettres <math>a</math> et <math>b</math>, et dont la <math>n</math>-ième lettre est un <math>a</math>, en d'autres termes :
:<math>K_n=\{a,b\}^{n-1}a\{a,b\}^*</math>.
Ce langage est reconnu par un automate à <math>n+1</math> états plus un état puits, mais son transposé, une fois déterminisé, requiert <math>2^n</math> états<ref name="BBCF"/>. 

Il a été observé<ref name="BBCF">{{harvsp|Berstel|Boasson|Carton|Fagnot|2010|p=}}.</ref> 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<ref>{{harvsp|De Felice|Nicaud|2013}}.</ref>{{,}}<ref name="FeliceNicaud2016">{{harvsp|Felice|Nicaud|2016}}.</ref> 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 :
{{théorème|Proposition (Brzozowski)| Soit <math>\mathcal{A}</math> un automate fini déterministe accessible, et soit <math>\mathcal{A}^\sim=\det(\operatorname{\,tr}(\mathcal{A}))</math> l'automate fini déterministe complet accessible obtenu à partir de l'automate transposé par déterminisation et élimination des états inaccessibles. Alors l'automate <math>\mathcal{A}^\sim</math> est minimal et reconnaît le langage miroir du langage reconnu par <math>\mathcal{A}</math>.}}

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

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

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

== Notes et références ==
{{Références}}

== Bibliographie ==

* {{article|auteur= Janusz A. Brzozowski|titre=Canonical regular expressions and minimal state graphs for definite events|périodique=Proceedings of the Symposium on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, April 1962| pages = 529-561|année=1963|éditeur=Wiley|lieu=New York| url=http://maveric.uwaterloo.ca/reports/1963_MTA_Brzozowski.pdf}} 
* {{Ouvrage | langue=fr | prénom1=Jacques | nom1=Sakarovitch | titre=Éléments de théorie des automates | lieu=Paris | éditeur=Vuibert | année=2003 | pages totales=816 | isbn=978-2-7117-4807-5 | isbn10=2-7117-4807-3 | bnf=389897103 | zbl=1188.68177}}
* {{chapitre | prénom1=Jean | nom1=Berstel 
 | prénom2=Luc | nom2=Boasson | prénom3=Olivier | nom3=Carton 
 | prénom4=Isabelle | nom4=Fagnot | titre chapitre=Minimization of Automata | arxiv=1010.5318 
 | année=2010 | titre ouvrage=Automata: from Mathematics to Applications
 |éditeur=European Mathematical Society}}
* {{chapitre|auteur1= Sven De Felice|auteur2=Cyril Nicaud
 |titre chapitre=Brzozowski Algorithm Is Generically Super-Polynomial for Deterministic Automata
 |titre ouvrage=Developments in Language Theory - 17th International Conference|année=2013       
 |passage=179-190|doi=10.1007/978-3-642-38771-5_17
 |auteurs ouvrage= Marie-Pierre Béal et Olivier Carton (éditeurs)
 |éditeur= Springer-Verlag
 |collection=Lecture Notes in Computer Science
 |numéro dans collection = 7907
 |isbn      = 978-3-642-38770-8}}
* {{article|langue=en|nom1=Felice|prénom1=Sven De|nom2=Nicaud|prénom2=Cyril|titre=Average Case Analysis of Brzozowski's Algorithm|journal=International Journal of Foundations of Computer Science|volume=27|numéro=02|année=2016|pages=109–126|doi=10.1142/S0129054116400025}}


{{palette|Automates finis et langages réguliers}}
{{Portail|Informatique théorique}}

[[Catégorie:Automates finis et langages réguliers]]
[[Catégorie:Théorie des automates]]