Discussion :

[daftsider]

Bonjour a tous !!

Je dois réalisé la minimisation d'un automate par un programme java, moon probleme est que je maitrise parfaitement la minimisation manuelle sur papier, mais je n'arrive pas à l'automatisé...

Pour le java je me débrouilleré, mais j'aurai besoin de votre aide pour avoir un algorithme cohérent


voici un début d'algorithme (vous notterez le mélange algo+java )

Arraylist classe = new Arraylist<Arraylist>()
Arraylist<Etat> G1 = new Arraylist<etat> ;
Arraylist<Etat> G2= new Arraylist<etat> ;
Classe.add(G1) ;
Classe.add(G2) ;
G1 = so ; //so est une arraylist contenant tous les etats de sortie de mon automate...
G2 = tous les autres ;
A1 = Classe.get(1).get(1) ;
A2 = classe.get(1).get(2) ;
Boolean changement ; //me permettra de sav oir si j'ai réalisé des changement ou pas (condition de fin si false)


On parcourt ensuite tr ; //tr est une arraylist contenant toutes mes transitions (construit sur la forme {attribut,etat_debut,etat_fin})

1) Si etat_debut = A1 on regarde son attribut et son etat_fin que l’on stock :

attrib = tr.get(i).getattribut() ;
fin = tr.get(i).getetatfin() ;


2) on reparcourt alors tr a la recherche cette fois de la condition
SI etat_debut=A2 alors
Si tr.get(j).getattribut() == attrib alors
Si (tr.get(j).getetatfin && fin) Є au meme Gi alors j++ et on remonte 2)
Sinon on crée une nouvelle arraylist<etat>


//c'est ici que je bloque car je ne sais pas comment appelé mon arraylist, je voudrais que ca suive la logique G3, G4, G5 mais je ne sais pas comment faire, ni meme si cela a un interet...

[ZZelle]

G0, G1, G2, G3 .... ça ne te fait pas penser à un tableau ?

Je ne peux pas t'aider bcp plus vu que je ne comprends pas grd chose à ton algo (pourtant je connais bien la méthodo pour implémenter une minimisation d'automates à sortie).

Mais j'ai l'impression que ce que tu as besoin ce n'est pas des Gi / G[i] qui pour la i-ème classe d'équivalence liste les états de la classe, mais plutôt l'inverse : le tableau C[e] qui a un état e associe C[e] qui est la classe d'équivalence à laquelle e appartient.
En effet tu veux transformer tr : {attribut,etat_debut,etat_fin} en TR : {attribut, C[etat_debut], C[etat_fin]}

En plus, C est un tableau dont la taille est déterminée dès le début par le nombre d'états (connu) contrairement à G & les G[i]

[Alikendarfen]

Bonjour,

Après une petite recherche sur http://fastnet.univ-brest.fr/~gire/C...P/node205.html,
via Google...

Deux états de l'AFD ont la même classe dans l'AFD minimal, si leur classe de départ (et ensuite courante) est la même et si les classes des états accessibles via les transitions sont toutes les mêmes.

Je te propose une méthode basée sur un tri des états, selon leur classe et les classes des états accessibles via les transitions de chaque état.

Pour les états, créer une classe Etat comprenant les informations suivantes :
- Numéro de l'état.
- Classe de l'état.
- Les transitions : un tableau d'états vers lesquels chaque transition pointe pour cet état.

Pour les classes, créer une classe ClasseDEtat :
- Numéro de la classe.
- Liste des états de la classe.

Avec ça, tu atteinds la classe de l'état d'une transition i depuis un état e par : e.Transitions[i].Classe.

Ton AFD est une liste d'états et une liste de classes, tel que décrit ci-avant.

Pour chaque classe :

1/ On va trier la liste des états de cette classe selon la liste des classes accessibles selon ses transitions.

2/ Ensuite, on parcourt la liste en gérant les ruptures, par classes accessibles selon les transitions.

A chaque rupture, tu affectes une nouvelle classe à ton état.

3/ Si aucune rupture n'est trouvée : c'est fini pour cette classe.
Sinon, on recommence 1/ 2/ 3/.

Je ne suis pas du tout spécialiste de la question (j'ai découvert le sujet à l'occasion de ton post) : il y a donc surement plus efficace comme algo. Mais peut être cela pourra t'aider.

Pour te mettre le pied à l'étrier une partie du code (la trame principale, en C#) :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
    public void Minimiser()
    {
        Queue<ClasseDEtat> classesATraiter = new Queue<ClasseDEtat>( ClassesDeDepart );
 
        ClassesDuResultat = new List<ClasseDEtat>();
 
        while ( classesATraiter.Count != 0 )
        {
            ClasseDEtat classe = classesATraiter.Dequeue();
 
            classe.Etats.Sort( Comparateur ); // Trier les états de la classe comme indiqué ci avant.
 
            List<ClasseDEtat> nouvellesClasses = new List<ClasseDEtat>();
 
            bool rupture = false;
            foreach ( Etat etat in classe.Etats )
            {
				// Si les classes des transitions de cet état ne sont pas celles du précédent :
				//		rupture = true
				//		affecter de nouvelles classes
            }
 
            if ( rupture )
                // Ajouter les nouvelles classes aux classes à traiter
            else
                ClassesDuResultat.Add( classe );
        }
    }
 
    // Compare les classes des états qui sont transitions pour e1 et e2.
    // Retourne -1 (e1 plus 'petit' que e2) 0 (si égalité) 1 (e1 plus 'grand' que e2).
    int Comparateur( Etat e1, Etat e2 ) 
    {
        Etat[] te1 = e1.Transitions;
        Etat[] te2 = e2.Transitions;
 
        for ( int i = 0 ; i < te1.Length ; i++ )
        {
            int cmp = te1[i].Classe.Numero.CompareTo( te2[i].Classe.Numero );
 
            if ( cmp != 0 )
                return cmp;
        }
        return 0;
    }

[ZZelle]

Pour chaque classe :

1/ On va trier la liste des états de cette classe selon la liste des classes accessibles selon ses transitions.

2/ Ensuite, on parcourt la liste en gérant les ruptures, par classes accessibles selon les transitions.

A chaque rupture, tu affectes une nouvelle classe à ton état.

3/ Si aucune rupture n'est trouvée : c'est fini pour cette classe.
Sinon, on recommence 1/ 2/ 3/.

Ya une petite erreur :

Il faut faire 1/ 2/ 3/ pour toutes classes.
Si au moins une "rupture" est trouvée dans au moins une classe on recommence pour toutes les classes & pas seulement celle qui a une "rupture"

[Alikendarfen]

Oui, exact,

Merci ZZelle