Automate fini non déterministe

Version imprimable

24/11/2013, 21h28
yonna

Automate fini non déterministe

Bonjour ;
je dois ecrire un programme en c qui permet de implementer une automate fini non deterministe mais avec les structures de données !!!:?
mercii d'avance
25/11/2013, 20h09
Bayard

Bon courage.

Où est votre code ?

Citation:

Envoyé par Bayard

Bon courage.

Où est votre code ?

salut;
le probleme c'est on doit utilisé les structures de données voici la structure donnée par le prof :

Code:

1
2
3
4
5
struct etat{
                                          int e;//e est le numero de etat enter 
                                          etat*next;//pointeur vers l'etat suivante
                                          };
                                      etat*tr[][];//un tableau de pointeur sur la structure

par exemple tr[0][0].e = 1
tr[0][0].e = 2

voici ce que j'ai fais

Code:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
liste construire()
{
        char condition1 [4],condition2 [4];
        etat* T=NULL;
		int l=0;
		int netats, nfinales,nsymboles;
     int f[10];
     int i,j;
     printf("enter le nombre des etats \n");
     scanf("%d",&netats);
     printf("enter le nombre des symboles \n");
     scanf("%d",&nsymboles);
     printf("\nenter les symbols\t");
 
     for(i=0; i<nsymboles; i++) 
     {
           printf("\n\n %d \t", i+1);
           printf("%c",c[i]=getch());
     }
 
     printf("\n\nenter le number des etats finaux\t");
     scanf("%d",&nfinales);
 
     for(i=0;i<nfinales;i++)
     {
          printf("\n\netat final %d : ",i+1);
          scanf("%d",&f[i]);
     }
 
     printf("-----------------------------------------------------------------------");
     printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
     tr=(int **) malloc(nsymboles*sizeof(int*)); 
     for (i=0; i<nsymboles; i++) 
      tr[i]=(int *) malloc(netats*sizeof(int)); 
   do{
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){
                    while(l=0);
               {printf("\n donner un etat");
               scanf("%d",(tr[i][j])->e));
                 if(tr[i][j]->e==-1) return 0;
               tr[i][j]->next=*T;
               *T=tr[i][j];
               printf("Voulez vous ajouter d'autres etats pour cette transition ? (oui/non)\n");
			   scanf("%s",condition1);
		    	l=strcmp(condition1,"non");
		    }
    }}
          while(l=0);      
    for(i=0; i<nsymboles; i++)
          for(j=0; j<netats; j++)
                  tr[i][j]=T;
           do
			{
      for(i=0; i<nsymboles; i++)
       {
          for(j=0; j<netats; j++)
               {printf("\n(%d , %c ) = ",j,c[i]);
               scanf("%d",tr[i][j]->e);
			   tr[i][j]=tr[i][j]->next;
				if ((next==NULL)||(tr[i][j] !=next->T)) l=1;
				else l=0;
			    }}}
			while ((tr[i][j]!= 0) &&  l!=0);
			return (liste)T;}}}
int main()
{
    char rep[3];
			int finale[1],i,nb;
			//liste k=construire();
			do
			{
                  liste k=construire();
 
	         }
		while(strcmp(rep,"non")!=0);
			return 0;
}

26/11/2013, 19h29
Bayard

1) J'ai vu des malloc mais je n'ai pas vu de free. Il faut prévoir cela même si c'est dans une fonction à part.

2) Si le prof demande d'utiliser cette structure, il ne demande pas forcément de l'utiliser avec une gestion dynamique de mémoire (malloc).
Pourquoi ne pas avoir un tableau en dur (const) qui contienne les états ?
Cela s'appelle de la gestion statique de mémoire.
Ce serait beaucoup plus simple. Ensuite faire des fonctions qui utilisent ce tableau de structure

Code:

struct etat

est assez facile...

Salut, premièrement merci de votre réponse :)
bon j'ai essayé de changer un peu algorithme mais toujours il y a des problèmes dans cette partie

Code:

1
2
3
4
5
{printf("\n donner un etat");
               scanf("%d",&((tr[i][j])->e));
                // if(tr[i][j]->e==-1) return 0;
                 ((tr[i][j]))->next=*T;
                 *T=tr[i][j]

voici tout le programme

Code:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stddef.h>
#include<string.h>
#include<stdlib.h>
char c[10];
struct etat
{
   int e;
   struct etat* next;
};
typedef struct etat etat;
 
typedef etat* liste;   
 
  void  construire(liste *T)
{
        char condition1 [4],condition2 [4];
        //etat* T=NULL;
		int l=0;
		int netats, nfinales,nsymboles;
		etat*tr[10][10];
     int f[10];
     int i,j;
    // int tr[10][10];
     printf("enter le nombre des etats \n");
     scanf("%d",&netats);
     printf("enter le nombre des symboles \n");
     scanf("%d",&nsymboles);
     printf("\nenter les symbols\t");
 
     for(i=0; i<nsymboles; i++) 
     {
           printf("\n\n %d \t", i+1);
           printf("%c",c[i]=getch());
     }
 
     printf("\n\nenter le number des etats finaux\t");
     scanf("%d",&nfinales);
 
     for(i=0;i<nfinales;i++)
     {
          printf("\n\netat final %d : ",i+1);
          scanf("%d",&f[i]);
     }
 
     printf("-----------------------------------------------------------------------");
     printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");
 
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){
                  { printf("donner les etats:");
                   scanf("%d",&tr[i][j]);}}
     for(i=0; i<nsymboles; i++)
    {
          for(j=0; j<netats; j++){  
                    while(l=0);
               {printf("\n donner un etat");
               scanf("%d",&((tr[i][j])->e));
                // if(tr[i][j]->e==-1) return 0;
                 ((tr[i][j]))->next=*T;
                 *T=tr[i][j];
               printf("Voulez vous ajouter d'autres etats pour cette transition ? (oui/non)\n");
			   scanf("%s",condition1);
		    	l=strcmp(condition1,"non");
		    }
    }}
          while(l=0);  }    }
   /* for(i=0; i<nsymboles; i++)
          for(j=0; j<netats; j++)
                  tr[i][j]=T;
           do
			{
      for(i=0; i<nsymboles; i++)
       {
          for(j=0; j<netats; j++)
               {printf("\n(%d , %c ) = ",j,c[i]);
               scanf("%d",tr[i][j]->e);
			   tr[i][j]=tr[i][j]->next;
			    }}}
			while ((tr[i][j]!= 0) &&  l!=0);
			return (liste)T;}}*/
int main()
{
    char rep[3];
			int finale[1],i,nb;
			//liste k=construire();
			liste T=NULL;
			do
			{
                  construire(&T);
 
	         }
		while(strcmp(rep,"non")!=0);
			return 0;
}

27/11/2013, 08h06
Bayard

1) Ma remarque 2 n'est pas prise en compte, il n'y a pas de tableaux de structure en dur (const).

2)La variable

Code:

etat*tr[10][10]

est une variable locale. Elle sera donc perdue en sortant de la fonction.
Donc tout pointeur qui y réfère sera cassé.

3) S'il y a un tableaux structure déjà construit "en dur" (const), il n'y a pas besoin de fonction qui s'appelle construire.
27/11/2013, 12h16
Médinoc

Ça me paraît bizarre de gérer les états par une liste chaînée, surtout avec un tableau 2D de pointeurs pour les transitions.

Pour moi, dans un AFN, on gérerait plutôt un tableau fixe d'états, et un tableau de Booléens pour chaque transition (et donc, ~~un tableau 2D de Booléens pour la liste de transitions~~ un tableau 3D de Booléens pour chaque transition vu qu'il y a NB_ETATS*NB_SYMBOLES transitions).

Salut,
merci pour les remarques ,mais je vais essayer les listes chainées multiple voici les structure:
Code:

1 2 3 4 5 6 7 8 9 10 struct etat{ int e; char s; etat*next; EA*suivant; }; struct EA{ int ea; EA * suivant; };
si vous avez des remarques n'hésitez pas pour m'aider à résoudre ce problème
cordialement .

27/11/2013, 13h59
Médinoc

Que signifie "EA" ?
27/11/2013, 19h12
yonna

Citation:

Envoyé par Médinoc

Que signifie "EA" ?

EA est une structure des états arrivés pour que structure etat qui contient etat et le symbole pointe sur une liste des etats arrive par exemple :
[1|a|.]-->[1|.]->[2|.]->null et ainsi de suite
27/11/2013, 21h29
Médinoc

Si ta structure contient un état et un symbole, elle devrait s'appeler transition, pas etat.

Citation:

Envoyé par yonna

merci pour les remarques ,mais je vais essayer les listes chainées multiple

Bonjour

Je sens que c'est pas super maitrisé...
Citation:
Envoyé par yonna
voici la structure donnée par le prof :
Code:

1 2 3 4 5 struct etat{ int e;//e est le numero de etat enter etat*next;//pointeur vers l'etat suivante }; etat*tr[][];//un tableau de pointeur sur la structure
Ca m'étonnerait qu'un prof ait pu pondre ça. Ou alors c'était un prof de chimie, physique, français, maths, histoire, sport, biologie, bref tout sauf de C. Déjà d'une part parce que "etat" ce n'est pas un nom de type donc "etat*next" ça ne compilera pas (faudrait écrire struct etat *next) et un tableau de pointeurs n'a pas besoin d'être en deux dimensions (et cette ligne non plus ne compilera pas). Et je vois mal un prof conseiller une variable globale... et en plus avec un nom aussi peu représentatif !!!
Citation:
Envoyé par yonna
voici les structure:
Code:

1 2 3 4 5 6 7 8 9 10 struct etat{ int e; char s; etat*next; EA*suivant; }; struct EA{ int ea; EA * suivant; };
si vous avez des remarques n'hésitez pas pour m'aider à résoudre ce problème
Ben déjà, en dehors du problème de syntaxe, le compilo ne peut pas connaitre "EA*suivant" si la structure EA n'a pas été déclarée .
Ensuite si tu veux être à l'aise il te faut commencer par être méthodique et rigoureux et poser les bases avec des noms appropriés et ne pas mettre des noms comme "ea" d'un coté et "EA" de l'autre ou "next" d'un coté et "suivant" de l'autre (super la relecture !!!).
Donc déjà les noms tout en majuscules sont réservés aux macros. Ensuite, une structure se préfixe par un "s_" et un type par un "t_". Et certains vont même jusqu'à préfixer leurs pointeur par autant de "p" qu'il y a d'étoile (char ***pppTruc) mais bon perso je ne le fais pas donc je ne peux pas te dire de le faire...

Ainsi, tes structures pourraient être
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct s_etatFini { int valeur; struct s_etatFini *next; } t_etatFini; typedef struct s_transition { int valeur; char symbole; struct s_transition *next; t_etatFini *etat; } t_transition;
Maintenant tu as maintenant deux beaux types "t_etatFini" et "t_transition" disponibles pour tes variables "etatFini" et "transition" si tu as envie de les nommer ainsi. Ensuite donc poser tes algos, faire des dessins de tes listes sur papier, schématiser l'insertion et la suppression puis une fois tout ça bien carré, le découpage de ton code en fonctions te viendra bien plus facilement...