Discussion :

[snipes]

salut les amis comment ca va ?

mon petit soucis du jour c'est que je dois faire un algorithme permettant d'effectuer la minimisation d'un automate

j'ai pu faire la premiere partie de cet algo (la plus clair a mon avis) qui consiste a retirer les etats inaccessibles
Cependant je ne parviens pas a trouver comment minimiser ce dernier en utilisant la definition ci dessous (2e partie de l'algo)

1 - Faire deux classes : A contenant les états terminaux et B contenant les états non terminaux.
2 - S'il existe un symbole a et deux états e1 et e2 d'une même classe tels que et n'appartiennent pas à la même classe, alors créer une nouvelle classe et séparer e1 et e2.
3 - Recommencer 2 jusqu'à ce qu'il n'y ait plus de classes à séparer.
4 - Chaque classe restante forme un état du nouvel automate

si quelqu'un peut m'expliquer l'etape 2 avec un (ou des) exemple(s) si possible et avec des mots simple je ne pourrais que le remercier du mieux que je pourrais

Merci

[FR119492]

Salut !

Je pense qu'il n'y a pas de réponse à ta question parce qu'il manque quelque chose au point 2 de ta citation:

d'une même classe tels que ????? et ????? n'appartiennent pas

Jean-Marc Blanc

[PRomu@ld]

En fait, la minimisation se fait sur un tableau. L'as-tu déjà fait à la main ?

En fait c'est relativement simple (rien n'est compliqué),

Tu prends deux éléments (A et B) d'une même classe, tu regardes leur état d'arrivée après application d'une transition a.

Si après application de la transition, ils arrivent dans des états qui appartiennent à la même classe alors après cette étape de l'algo ils seront dans la même classe.

Admettons que tu ais deux classes, disons A les non terminaux et B les terminaux :

A = { 1 , 2 , 3 , 4 , 5 } ; B = { 6 , 7 }

Admettons aussi que tu ais les transitions suivantes :

(1,a,6)
(2,a,4)
(3,a,3)
(4,a,5)
(5,a,1)

lorsque tu appliques la transition A, les états 1 et 2 ne mènent pas vers les mêmes classes (1 mène vers un état de la classe B alors que les autres mènes vers un état de la classe A). Il faut donc éclater la classe A en deux classes pour avoir ta nouvelle partition :

A1 = { 1 } A2 = { 2 , 3 , 4 , 5 } et B = { 6 , 7 }

[snipes]

ok merci pour l'exemple cette fois ci jcrois que j ai compris
j'attaque des maintenant l'algo tant que c'est frais dans mon esprit
je vous tiens au courant !