Informatique

Bonjour,

Je poste ce message pour avoir une petite confirmation au sujet de la minimisation d'automate.

Imaginons l'automate suivant :

Etat 1 : En a : va en 3; En b : va en 1
Etat 2 : En a : va en 3, En b : va nulle part
Etat 3 (final) : En a : va en 3, En b : va en 1

SI ensuite, je veux minimiser cet automate, lors de la première itération, j'obtiens le schéma suivant :

1 2 3
0 I I II
a II II II
b I / I

Donc pour 1 on a le chemin : I - II - I et pour 2 : I - II - /
Donc je voulais la confirmation, ces chemins sont donc bien différents ? Le fait que l'état 2 n'admette aucune transition en B, ne change pas le comportement de l'algo ?

Merci !

Oui. Ton automate est déterministe, mais un AF déterministe n'est pas forcément complet.

D'accord ! Merci à toi !

Il faut faire attention quand ton automate n'est pas complet. Il faut d'abord commencer par compléter ton automate en rajoutant un etat puits : tu rajoutes un état 4 (non final), la transition de 2 vers 4 en lisant b, et des transitions de 4 vers 4 en lisant a et en lisant b.

Ensuite, tu fais l'algo de minimisation dans ce nouvel automate complété.

Sur ton exemple ça donne le même résultat, mais dans le cas général il peut y avoir une différence.

Donc avant chaque minimisation, je dois compléter mon automate avec un état poubelle (s'il n'est pas complet) ?

Oui, il faut supprimer les états non-accessibles, et le compléter, puis ensuite faire la minimisation.

D'accord merci à toi !