Méthode de Brzozowski et McCluskey

En informatique théorique, et notamment en théorie des automates, la méthode de Brzozowski et McCluskey, aussi appelée méthode d'élimination d'états (« state elimination method »), est une méthode permettant d'obtenir une expression rationnelle à partir d'un automate fini. L'algorithme porte le nom de ses inventeurs, J. A. Brzozowski et E. J. McCluskey, qui l'ont présenté en 1963. L'algorithme est exposé dans plusieurs manuels[1],[2] ou des cours[3]. La méthode est également appelée algorithme de Kleene.

Principe

L'algorithme utilise de façon intensive la représentation graphique de l'automate. L'automate lui-même est généralisé, en autorisant, comme étiquettes des transitions, non seulement des lettres, mais des expressions rationnelles. Partant d'un automate fini, on élimine progressivement les états. À la fin, l'automate n'a qu'une seule transition, de l'état initial à l'état final, étiqueté par une expression rationnelle dénotant le langage reconnu par l'automate.

Automate généralisé

Un automate généralisé est défini comme un automate fini non déterministe traditionnel, avec les particularités suivantes :

• il possède un seul état initial α et un seul état final ω ;
• les transitions sont étiquetées par des expressions rationnelles ;
• aucune transition n'entre dans α et aucune transition ne sort de l’état final ω.

Un mot w est reconnu par l'automate généralisé s'il existe un chemin allant de α à ω tel que w appartient au langage dénoté par le produit des expressions régulières apparaissant comme étiquettes de ce chemin. Le langage reconnu est l'ensemble des mots reconnus. Deux automates sont équivalents s'ils reconnaissent le même langage.

On peut facilement transformer un automate ordinaire A en un automate généralisé : il suffit d'ajouter les états α et ω et des ε-transitions de α vers les états initiaux de A, et des ε-transitions des états terminaux de A vers ω.

Algorithme

Étant donné un automate généralisé, on calcule un automate généralisé ayant moins de transitions ou d'états, en appliquant les transformations ci-dessous sans modifier le langage reconnu. À la fin, il ne reste que les deux états α et ω et une transition de α et ω dont l'étiquette est une expression régulière dénotant le langages reconnu. Les transformations sont des réductions des transitions et des réductions des états.

Réduction des transitions

On remplace deux transitions ${\displaystyle (p,r,q)}$ et ${\displaystyle (p,s,q)}$ par la transition ${\displaystyle (p,r+s,q)}$:

• 
  Réduction des transitions.

Réduction des états

On enlève un état ${\displaystyle k}$ choisi, et pour chaque couple ${\displaystyle (p,q)}$ d'un prédécesseur ${\displaystyle p}$ de ${\displaystyle k}$ et d'un successeur ${\displaystyle q}$ de ${\displaystyle k}$, on remplace les transitions ${\displaystyle (p,r,k),(k,s,k)}$, et ${\displaystyle (k,t,q)}$ par ${\displaystyle (p,rs^{*}t,q)}$ s'il y a une transition ${\displaystyle (k,s,k)}$, et par ${\displaystyle (p,rt,q)}$ sinon.

• 
  Réduction des états.

Exemple

Considérons l'automate suivant (qui reconnaît l'ensemble des mots contenant un nombre impair de lettres a).

• 
  Automate de départ.

Après adjonction des états α et ω, on élimine progressivement l'état 2 puis l'état 1.

• 
  Automate après l'adjonction des états α et ω.
• 
  Automate après l'élimination de l'état 2.
• 
  Automate après l'élimination de l'état 1.

On obtient l'expression rationnelle ${\displaystyle (b+ab^{*}a)^{*}ab^{*}}$qui caractérise le langage reconnu par l'automate de départ.

Notes et références

1. Carton 2008.
2. Sakarovitch 2003.
3. Désarménien.

Bibliographie

• J. A. Brzozowski et E. J. McCluskey, « Signal Flow Graph Techniques for Sequential Circuit State Diagrams », IEEE Transactions on Electronic Computers, Institute of Electrical & Electronics Engineers (IEEE), vol. EC-12, n^o 2,‎ avril 1963, p. 67-76 (DOI 10.1109/pgec.1963.263416).
• Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
• Jacques Désarménien, « Automates. Chapitre 1.5 Équivalence des modèles », Université Paris-Est Marne-la-Vallée (consulté le 16 juin 2016).

Articles connexes

• Automate fini
• Automate fini déterministe
• Automate fini non déterministe
• Théorie des automates
• Algorithme de McNaughton et Yamada
• Lemme d'Arden
• Algorithme de Conway
• Algorithme de Thompson