Algorithme de Brzozowski et McCluskey

Algorithme de Brzozowski et McCluskey

L’algorithme de Brzozowski et McCluskey 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 régulières. Partant d’une automate fini, on élimine progressivement les états, et à la fin, on se retrouve avec un automate ayant une seule transition. L’étiquette de cette transition est une expression rationnelle pour le langage reconnu par l’automate.

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 ω.

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 ω.

Réduction de l’automate

É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.

Pour réduire un état, il faut effectué tous les chemins passant par cet état (vers un état adjacent). Le langage reconnu par ce chemin est alors ajouté à l’automate réduit (voir l’exemple).

L’exemple suivant montre les principales réductions possible ainsi que les expressions rationnelles engendrées sur l’automate :

Qui donne l’automate généralisé suivant :

On élimine q2 : le chemin q0 -> q2 -> q3 donne le langage a², il est donc ajouté au chemin q0 -> q3. Le chemin q3 -> q2 -> q3 donne le langage ba ou (ba)* car il s’agit d’une boucle sur q3 -> q3

On élimine q1 : ici la boucle sur q1 donnera une a*

On élimine q0 :

On élimine q3 :

Notons que l’expression obtenu dépend aussi de l’ordre d’élimination, mais que tous les langages générés sont égaux.