[Automate] Minimisation
Résolu
bejaia
-
humel -
humel -
Bonsoir
Je sais comment déterminiser un automate.
Quelqu'un pourrait-il m'expliquer commant minimiser un automate d'après cet exemple page 8 (vignette 29 et 30).
http://deptinfo.unice.fr/~julia/AL/02al.pdf
Je bloque malgré la définition. Donc merci de détailler pas à pas.
obtenir un automate ayant le minimum d'états possible. En effet, certains états peuvent être équivalents.
Principe : on définit des classes d'équivalence d'états par raffinements successifs. Chaque classe d'équivalence obtenue forme un seul même état du nouvel automate.
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
merci d'avance
Je sais comment déterminiser un automate.
Quelqu'un pourrait-il m'expliquer commant minimiser un automate d'après cet exemple page 8 (vignette 29 et 30).
http://deptinfo.unice.fr/~julia/AL/02al.pdf
Je bloque malgré la définition. Donc merci de détailler pas à pas.
obtenir un automate ayant le minimum d'états possible. En effet, certains états peuvent être équivalents.
Principe : on définit des classes d'équivalence d'états par raffinements successifs. Chaque classe d'équivalence obtenue forme un seul même état du nouvel automate.
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
merci d'avance
A voir également:
- Minimisation d'un automate
- Comment faire un sommaire automatique sur word - Guide
- Comment lancer un programme automatiquement au démarrage de windows - Guide
- Télécharger logiciel automate programmable gratuit - Télécharger - Émulation & Virtualisation
- Barbara veut calculer automatiquement son budget dans un tableau ✓ - Forum finances
- Barbara veut calculer automatiquement son budget dans un tableau. citez un des logiciels lui permettant de faire des calculs sur des tableaux de nombres (tableur). - Forum Musique / Radio / Clip
3 réponses
bonjour !
je veux avoir un programme sur C pouvant representer un automates à etats finis ,avec la possibilité de désambiguisation
et la minimisation ;
merci d'avance .
je veux avoir un programme sur C pouvant representer un automates à etats finis ,avec la possibilité de désambiguisation
et la minimisation ;
merci d'avance .
Salutations,
Je vais tenter un déroulement de l'algo seulement ça date un peu et aussi, je le prends pas dans le même sens que ce qui est expliqué dans ton pdf. Plutôt que de faire des groupes et de les casser en cas de conflit des membres, je prends tout le monde à part et je regroupe.
Pour l'exemple B donc, on part de l'automate déterministe (on verra vite pourquoi d'ailleurs...)
On fait une colonne pour des états et les autres colonnes pour l'alphabet.
Pour l'exemple A:
Pour la méthode indiquée plus directement dans le pdf, je te laisse trouver comment organiser le déroulement de l'algo. L'idée est dans chaque groupe de vérifier que tous les états mènent au même état (/groupe). Si ce n'est pas le cas c'est que certains états du groupe n'ont pas le même comportement que leurs voisins et doivent donc quitter le groupe pour arriver au final à des groupes dont tous les états sont d'accord entre eux. Ca doit pouvoir se poser sous forme de tableaux aussi...
C'est peut-être plus sage d'essayer de retrouver la voie normale expliquée dans les règles.
M.
Je vais tenter un déroulement de l'algo seulement ça date un peu et aussi, je le prends pas dans le même sens que ce qui est expliqué dans ton pdf. Plutôt que de faire des groupes et de les casser en cas de conflit des membres, je prends tout le monde à part et je regroupe.
Pour l'exemple B donc, on part de l'automate déterministe (on verra vite pourquoi d'ailleurs...)
On fait une colonne pour des états et les autres colonnes pour l'alphabet.
1ère itération: On part de l'état initial / a b _____ 0 1 2 0 arrive en 1 par a et en 2 par b. Suite des événement: on a deux nouveaux états à traiter 1 4 3 2 3 5 4 6 2 3 6 6 - 5 6 3 6 6 6 - On a fait tous les états apparus, on regroupe ceux qui ont des lignes identiques. (Puisqu'ils ont exactement le même comportement) Attention cependant on ne regroupe pas les finaux avec des non finaux. 2ème itération: On part de l'état initial / a b ___________ 0 1 2 1 4 36 2 36 5 4 36 2 36 36 36 (final) 5 36 36 (non final) Plus d'état ayant leurs lignes identique, fin de l'algo. En passant on voit bien pourquoi il faut rendre déterministe l'automate avant d'appliquer cet algo, sinon, ça rentre pas dans les cases ^^"
Pour l'exemple A:
1ère itération: / a b _____ 0 1 2 1 4 3 2 3 5 4 6 6 - 3 6 6 - 5 6 5 6 6 6 - 2ème itération: / a b ___________ 0 1 2 1 346 346 - 2 346 5 -- 346 346 346 - 5 346 5 -- 3ème itération: / a b ______________ 0 1346 25 - 1346 1346 1346 25 1346 25 - 4ème itération: / a b _______________ 025 1346 025 1346 1346 1346 Plus de lignes identiques, fin.
Pour la méthode indiquée plus directement dans le pdf, je te laisse trouver comment organiser le déroulement de l'algo. L'idée est dans chaque groupe de vérifier que tous les états mènent au même état (/groupe). Si ce n'est pas le cas c'est que certains états du groupe n'ont pas le même comportement que leurs voisins et doivent donc quitter le groupe pour arriver au final à des groupes dont tous les états sont d'accord entre eux. Ca doit pouvoir se poser sous forme de tableaux aussi...
C'est peut-être plus sage d'essayer de retrouver la voie normale expliquée dans les règles.
M.
Mahmah ta méthode est incomplete, il est suffisant que les lignes soit identiques pour fusionner les etats, mais ce n'est pas une condition necessaire, exemple :
0 initial
2 final
a b
0 0 2
1 1 2
2 0 1
on peut fusionner l'etat 0 et 1 malgre que les lignes ne soient pas identiques, en effet cette automate est equivalent a :
a b
01 01 2
2 01 01
je penses que tu vas devoir réviser ta méthode, ou comme tu l'as indiqué il serait plus sage d utiliser l'algo de kleene
0 initial
2 final
a b
0 0 2
1 1 2
2 0 1
on peut fusionner l'etat 0 et 1 malgre que les lignes ne soient pas identiques, en effet cette automate est equivalent a :
a b
01 01 2
2 01 01
je penses que tu vas devoir réviser ta méthode, ou comme tu l'as indiqué il serait plus sage d utiliser l'algo de kleene
