[Automate] Minimisation
Résolu/Fermé
A voir également:
- Minimisation d'un automate
- Comment faire un sommaire automatique sur word - Guide
- Virginie organise un rallye avec 30 équipes. elle veut créer un code pour désigner chaque équipe. elle a commencé à la main, mais elle voudrait le faire calculer automatiquement. trouvez ce qu'elle veut faire puis proposez une formule à recopier vers le bas dans la colonne a. quelle formule sera en a9 ? - Forum Excel
- Comment minimiser la taille d'un fichier pdf - Guide
- Je veut créer des codes ✓ - Forum Programmation
- Dépôt chèque lcl automate - Forum logiciel systeme
3 réponses
access2008
Messages postés
7
Date d'inscription
dimanche 24 février 2008
Statut
Membre
Dernière intervention
4 mars 2010
4 mars 2008 à 11:11
4 mars 2008 à 11:11
je suis en train de faire une solution ..
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 .
Mahmah
Messages postés
496
Date d'inscription
lundi 17 septembre 2007
Statut
Membre
Dernière intervention
22 juin 2010
125
7 mars 2008 à 11:15
7 mars 2008 à 11:15
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