Minimisation d’un AFD

Difficulté
Moyen 50%

Minimisation d’un AFD

Théorème de Myhill-Nérode (minimisation d’un AFD). Soit L un langage rationnel. Parmi tous les AFD reconnaissant L, il en existe un et un seul qui a un nombre minimal d’états.

Avant de minimiser un AFD, il faut le compléter, c’est à dire rajouter un état poubelle comme l’état R sur le schéma ci-dessous.

minimisation d'un AFD

L’algorithme de minimisation est le suivant :

  1. Compléter l’AFD nommé D
  2. Construire une partition initiale ∏ contenant deux ensembles I et II d’états tel que ∏={I=(états terminaux d’acceptation de D), II=(autres états états de D)}
  3. Pour chaque état de D faire
    1. Construire la table de transition
    2. Marquer les états de départ et d’arrivées en fonction de leur groupe de ∏
  4. Si des états du même groupe de ∏ ont des comportements divergeant
    1. Séparer les états dans un nouveau groupe (III par exemple) – de préférence ne faire qu’une séparation par itération.
    2. Retourner à 3
  5. Fin : les nouveaux états sont les groupes de ∏

Exemple

Reprenons l’exemple de l’AFD ci-dessus. Il est bien déterministe comme le montre la table de transition.

Regardons la table de transition à l’étape 3 :

 abc
0(I)2(II)5(II)R(I)
2(II)R(I)R(I)R(I)
5(II)R(I)R(I)8(II)
8(II)R(I)R(I)8(II)
R(I)R(I)R(I)R(I)

Nous remarquons quand dans le groupe I, le comportement de O et de R divergent, nous allons donc les séparer en deux groupes: I=(0) et III=(R)

Voici la nouvelle table de transition :

 abc
0(I)2(II)5(II)R(III)
2(II)R(III)R(III)R(III)
5(II)R(III)R(III)8(II)
8(II)R(III)R(III)8(II)
R(III)R(III)R(III)R(III)

Nous remarquons quand dans le groupe II, le comportement de 2 et de 5, 8 divergent, nous allons donc les séparer en deux groupes: II=(5, 8) et IV=(2)

Voici la nouvelle table de transition :

 abc
0(I)2(IV)5(II)R(III)
2(IV)R(III)R(III)R(III)
5(II)R(III)R(III)8(II)
8(II)R(III)R(III)8(II)
R(III)R(III)R(III)R(III)

On n’observe plus de divergence entre les groupes, nous pouvons donc effectuer la table de transition avec l’AFD minimisé donnant la table de transition suivante :

 abc
IIVIIIII
IVIIIIIIIII
IIIIIIIIII
IIIIIIIIIIII

L’état inital est I (en rapport à son équivalent dans D), et les états terminaux de l’automate sont II et IV (en rapport à leurs équivalents dans D).

Autre exemple

Prenons l’automate suivant :

minimisation d'un AFD

La phase d’initialisation permet d’obtenir le groupe non terminal I et le groupe terminal II :

 ABCD
InitIIIIII

Regardons les transitions pour chaque état selon les groupes I et II :

AlphabetABCD
aIIIIIII
OIIIIII

Puis on effectue la séparation des ensembles. Deux états sont dans un même ensemble s’ils étaient déjà dans le même ensemble et si les transitions mènent dans les mêmes ensembles. Dans cet exemple, B et D se comportent exactement de la même manière, donc ils restent ensemble. Par contre, A et C qui faisaient partie du même ensemble se comportent différemment sur le symbole « a ». Par conséquent, l’ensemble noté I se divise en deux. Nous obtenons donc :

 ABCD
InitIIIIII
aIIIIIII
0IIIIII
Séparation 1IIIIIIII

La situation courante (la ligne Bilan 1) est différente que la situation de départ. Donc il faut recommencer.

 ABCD
InitIIIIII
aIIIIIII
0IIIIII
Séparation 1IIIIIIII
AIIIIIIIII
0IIIIIIIIII
Séparation 2IIIIIIII

La ligne « Séparation 2 » est identique à la ligne « Séparation 1 ». Par conséquent, dans chacun des ensembles restants, les états ne sont pas distinguables (ils se comportent exactement de la même manière et sont donc « redondants »).

Nous pouvons donc construire le nouvel automate en associant un état à chaque ensemble. Les transitions sont indiquées par le tableau. L’état initial est celui contenant l’état initial de l’automate de départ : ici I contient l’état A, état initial. Les états finaux sont les états dont l’ensemble correspondant contient au moins un état final : ici, II contient B et D qui sont finaux.

minimisation d'un AFD

Pour l’instant, nous avons « fusionné » les états indistinguables. Il faut maintenant supprimer tous les états inutiles restant. Dans notre exemple, l’état III est un état stérile (non terminal et sans transition), donc inutile. Il faut donc le supprimer. D’où l’automate déterministe minimal de la figure suivante :

minimisation d'un AFD
Partager
fr_FRFR
%d blogueurs aiment cette page :