algo de minimisation d'un automate/graph

Coucou a tous, je doit réduire ( minimiser) un automate déterministe donné . ( je l'ai modéliser sous forme d'un graphe )

Et j'ai un peu de mal a trouver une methode bien expliqué sur le web .
J'ai la méthode de moore dans le cours ; mais ca me depasse un peu .
J'ai cru voir que celle de brzozowski était plus simple, mais je n'ai trouvé qu'une seule source expliquant la méthode général et elle me parait bizzare ...
enfin si quelqun a une source pertinente et accessible ;) je prend !
merci d'avance !

edit: la page en question :
http://www.liafa.jussieu.fr/~mz/enseignement/04-05/Automates/TD.pdf

page 5, quand japlique la methode, je ne vois pas quelle transition vont disparaitre... selon moi aucune ...

En appliquant la méthode, tous les états non-accessibles de ton automate renversé vont disparaitre, et les transitions qui mènent à ces états. Les états accessibles de l'automate renversé correspondent aux états co-accessibles de ton automate de départ. Donc tous les états non-co-accessibles seront supprimés. Ton automate étant à la base accessible, tu auras donc un automaté émondé. Et comme tu as determinisé le tout, ca te donne effectivement un automate minimal. Par contre, vois si la complexité est meilleure que celle de l'algorithme de Moore.

re coucou !! ( pti retour de vacances, donc ma réponses va peut-etre etre a coté de la plaque, car je suis pas trés frais la lol ) .

Citation:

---

En appliquant la méthode

---

on parle bien de l'algo de brzozowski la ? ( c'est juste pour etre sur hein ^^ )

Citation:

---

tous les états non-accessibles de ton automate renversé vont disparaitre

---

Heu, l'automate renversé va etre mon auto minimal , non ? Donc quand tu parle de faire disparaitre certain de ses états je pige pas trop ...
Enfin on va admetre que tu parlais des états non-accessible de l'automate de départ, qui ne seront pas présent dans l'auto renversé ( cest ca? ) .
Si c'est le cas ... bah je vois pas comment ca se fait .
** Un état n'est pas accessible si aucun calcul ne mene de l'etat ini a cet état . **
En gros, dans notre cas, c'est un état inutile . Jusque la tout va bien . Par contre, ( état donné que la seule véritable modification de l'algo c'est d'inversé les transi -- ou alors j'ai pas le bon algo ) je ne vois pas comment cela va marcher ...

Pour le reste ..bah on va attendre d'avoir comprit le début ;)
merci et bonne nuit .

Citation:

---

Heu, l'automate renversé va etre mon auto minimal , non ? Donc quand tu parle de faire disparaitre certain de ses états je pige pas trop ...

---

Non, quand tu renverses ton automate, tu n'as encore enlever aucun état, donc il n'y a aucune raison pour que celui-ci soit l'automate minimal. Par contre, excuse moi, mais j'avais écrit:

Citation:

---

Les états non accessibles de l'automate renversé correspondent aux états co-accessibles de ton automate de départ

---

Qu'il fallait lire

Citation:

---

Les états accessibles de l'automate renversé correspondent aux états co-accessibles de ton automate de départ

---

ou

Citation:

---

Les états non accessibles de l'automate renversé correspondent aux états non co-accessibles de ton automate de départ

---

Un état co-accessible est un état à partir duquel tu peux attendre un état final. Donc les états co-accesibles de l'automate initial, deviennent des états accessibles dans l'automate renversé. En determinisant ce dernier, tu supprimes les états non accessibles (donc les co accessible de l'automate de base).

A la base tous les états de ton automate étaient accessibles. Ils sont donc tous coaccessibles dans ton automate renversé. Comme tu supprimes tous les accessibles dans ton automate renversé, ton automate renversé devient émondé, donc minimal.

L'algo consiste donc à appliquer cet astuce à ton automate renversé (en gros il faut renverser deux fois).
1 -> Renverser mon automate
2 -> Déterminiser l'automate
3 -> Re-renverser l'automate
4 -> Déterminiser l'automate
5 -> C'est dans la poche !

Citation:

---

1 -> Renverser mon automate
2 -> Déterminiser l'automate
3 -> Re-renverser l'automate
4 -> Déterminiser l'automate
5 -> C'est dans la poche !

---

oula ;) ca fait beacoup tout ca ^^ enfin, surtout de la facons dont j'ai déterminiser mon automate ( c'est pour un tp de cours, donc j'ai fait sa simplement, sans trop me préocuper de la réutilisation des choses ect ... )

Je vais regarder du coté de moore , si je trouve un algo assez simple a suivre ;) ( car tout ce que j'ai vu pour le moment est énoncé dans une forme qui m'échape un peu ... )

Enfin, merci de ces réponses, je vasi tout de meme analyser ca de plus prés dés que j'ai un peu plus de temps !

si tu veux l algorithme le plus optimal pour minimiser, c est l algorithme d hopcroft.

je suis tombé sur ce nom également durant mes recherche , mais je ne suis pas non plus parvenu a trouver une explication simple et complete de ce que c'était ...

Si c'est pour implémenter, je te recommande MOORE qui est quand même plus simple. L'avantage de celui qui vient d'être donner, c'est si tu as déjà coder la determinisation, tu n'as plus qu'à savoir renverser ton automate (assez fastoche) et hop le tour est joué.

Citation:

---

le plus optimal pour minimiser

---

Hum, en général un superlatif suffit. "L'algorithme de cout optimal", "L'algorithme le plus performant" ou "l'algorithme qui minimise le cout".

En théorie , oui, mais mon programme est horriblement coder .
Je cré un nouvel automate a l'aide de la fonction déterminiser .
Enfin c'est pas beau, pas générique, et pas ré-utilisable :( .
Quant a Moore, je me suis penché dessus cet aprés-midi .

Il ne s'aplique sur des automate complet et accessible . Mais bon passons .
J'avoue que le cours tel quel, ne me parle pas du tout . Et j'attendrai bien ma seance de TD pour voir de quoi il retourne , mais manque de chance, notre prof de TD n'est pas synchro avec celui de TP et nous fait la minisation 2 jour avant notre TD final alors qu'ont auraient du voir ca avant les vac ...
fin bref ...
je suis toujour en quete d'un lien ou l'algo serait déroulé pas a pas ( a la main ) sur un exemple précis ... je pense que ca me suffirai a en déduire l'algo ;)

enfin bon
/me y retourne

merchi :)

on va ire que j ai dit ca pour insister sur le fait que c'est l'algo qui a le cout le plus bas :p.

Sinon pour Hopcroft je conseil ce court qui est bien fait et qui te montre comment l'implementer (le groos anglicisme !!!) :
http://www-igm.univ-mlv.fr/~berstel/...ts/EAChap9.pdf

J espere que ca t aidera.