Discussion :

[Fredo123456]

Bonjour à tous,
Je dois réaliser un programme permettant de minimiser un automate donné. Pour cela je me suis renseigné sur Internet et j'ai trouvé une méthode relativement efficace: celle de utilisant l'algorithme de Moore.

Or je n'ai pas assez bien compris le fonctionnement de cette méthode avec ces sites pour pouvoir le programmer.
Votre aide me sera très utile... Merci beaucoup.

Voici le site qui m'a donné envie de faire cette méthode :
http://www-igm.univ-mlv.fr/~desar/Co...omates/ch2.pdf
(voir en bas de la page)

[3DArchi]

Bonjour,
Je pense que tu as plus besoin d'une explication sur l'algo que sur son implémentation pour commencer. Je déplace donc ta discussion vers le forum adéquat.

[Isythiel]

L'algo pour minimiser un automate est pourtant assez simple.

C'est le fait de regrouper les sommets en fonctions de leurs transitions.

Au début, tu as deux groupes : le premier contient tous les sommets sauf les terminaux, le deuxième contient uniquement les terminaux.

Ensuite il faut "boucler" :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
Pour chaque groupe,
   Pour chaque caractère
      Tant que tous les sommets ne transitent pas vers le même groupe
         scinder le groupe
      FinTQ
   FinPour
FinPour

Si tu ne comprends toujours pas, je t'aiderai à applique ça sur un exemple.

[Obsidian]

C'est un procédé très simple mais il est vrai qu'il n'est pas facile à expliquer en quelques mots. Par contre, une fois le principe compris, il devient trivial.

L'idée générale consiste à voir si tu peux écrire un automate qui rende les mêmes services qu'un autre automate donné en référence, mais en utilisant moins d'états. Le moins possible, en fait.

Pour cela, tu regroupes tous les états équivalents dans une même « famille ». En général, ce qui nous intéresse est de savoir si un état est final ou non-final, donc on commence généralement avec deux groupes - les finals et les non-finals - mais ce n'est pas une obligation. On pourrait imaginer par exemple un automate qui te serve à choisir l'enseigne d'une carte à jouer. Dans ce cas, chacun des états pourrait représenter un cœur, un pique, un trèfle ou un carreau. Tu ferais alors quatre groupes d'états et tu classerais chacun de ceux-ci dans un de ces groupes.

Ensuite, pour chaque transition, tu vérifies si les tous les états d'un groupe donnent, non pas sur un même état, mais sur un état quelquonque d'un même autre groupe. La clé de l'algo est là : si tous les états d'une même famille (donc équivalents) s'en vont vers les états d'une même autre famille, alors il n'y a plus de raison de les distinguer entre eux : ces deux familles peuvent être considérées chacune comme un état unique.

Si ce n'est pas le cas, alors tu vas diviser ton groupe, plus précisément le partitionner, en regroupant en son sein tous les états qui réagissent de la même manière pour chaque transition. Et ta famille en fait alors plusieurs. Ces nouveaux groupes deviennent donc des groupes à part entière (et pas des « sous-groupes »).

À ce stade, tu recommences le processus depuis le début. Et tu procèdes ainsi tant que ton automate continue à se fragmenter. Au bout d'un moment, le nombre de familles que tu obtiens et les états qu'elles contiennent sont exactement les mêmes qu'à l'opération précédente. Par conséquent, tu peux affirmer que le résultat sera aussi le même la fois suivante, et celles d'après. C'est donc à ce moment que tu sais que tu as fini.

Tu n'as plus qu'à réécrire le nouvel automate en fonction de ces résultats : pour chaque famille, tu traces un état dans ton nouvel automate. Et comme tous les états d'une même famille mènent, à la fin du processus, vers les mêmes autres groupes, tu en prends un au hasard et tu t'en sert pour tracer les transitions du nouvel automate.

Arrivé là, on peut faire trois observations :

• Chaque état d'un automate à minimiser fait forcément partie d'un groupe, et un seul ;
• Tu as au minimum deux groupes, et au maximum le même nombre de groupes que d'états. Si tu n'avais qu'un seul groupe au départ, celui-ci ne pourrait jamais se fragmenter. Cela voudrait dire également que tous les états sont équivalents et donc que l'automate ne sert à rien. Quand tu arrives à autant de groupes que d'états, cela veut dire qu'il y a un état par groupe et donc que l'automate ne peut pas être minimisé plus qu'il ne l'est déjà. Dans les deux cas, l'algorithme s'arrête de lui-même en rendant un résultat identique à celui de l'étape précédente ;
• Un groupe peut se fragmenter en plusieurs au cours de l'opération, mais plusieurs groupes ne peuvent en aucun cas fusionner en un seul. Si tu as deux groupes présentant les mêmes propriétés, ils restent deux groupes distincts, spécialement si ce sont ceux qui contiennent les états finals et non-finals ;