siwarga
Messages postés2Date d'inscriptionmardi 9 décembre 2014StatutMembreDernière intervention 9 décembre 2014
-
9 déc. 2014 à 11:41
Bonjour,
/*salut
voila mon programme qui fait la déterminisation d'un automate non déterministe..
mais il contient des erreurs,
je souhaitrai que vous m'aidiez à les détecter et corriger.
*/
#include<iostream.h>
#include<stdio.h>
/************************************************/
/*declaration de type liste intermidiaire qui cotient 02 champs*/
struct element{
char information;
element*suivant;
};
/*********************************************************************************/
/*declaration de type derivation qui cotient 04 champs*/
/*comme le type booleen n'exixte pas on doit le declarér comlme un entier*/
/* prend 02 valeur :0->faux///1->vrai*/
struct derivation{
char val;
char carectere;
unsigned final;
derivation*deriv_voisin;
};
/********************************************************************************/
/*declaration de type etat qui cotient 03 champs*/
struct etat{
char inf;
etat*etat_suiv;
derivation*deriv_suiv;
};
/******************************************************************/
struct graph
{
char info;
char arc;
graph *suivant;
};
/*********************************************************************************/
/*declaration de la fonction qui crée la liste des derivations*/
/********************************************************************************/
derivation cree_list_derivation(etat G,int x)
{
derivation s;
derivation v;
derivation p;
derivation q;
unsigned a;
unsigned b;
int i=1;
cout<<"entrer le nom du "<<i<<" derivation:"<<endl;
cin>>s.val;
cout<<"entrer la valeur de l'arc ou le carectere:";
cin>> s.carectere;
cout<<"si est un etat final entrer true:"<<endl;
cin>> b;
b=s.final;
q=s;
for (i=2;i<=x;i++)
{
//p=new(derivation);
s.deriv_voisin=p.deriv_voisin;
cout<<"entrer le nom du "<<i<<" derivation:";
cin>>p.val;
cout<<"entrer la valeur de l'arc ou le carectere:"<<endl;
cin>> p.carectere;
cout<<"si est un etat final entrer true:"<<endl;
cin>>a;
a=p.final;
p=s;
}
s.deriv_voisin=NULL;
return (q);
}
/*********************************************************************************/
/***declaration de la fonction qui crée la liste des etats***/
/***************************************************************************/
etat cree_list_etat(int x)
{etat p;
etat z;
etat q;
etat g;
etat a;
int n,i=1;
// p=new(etat);
g=p;
cout<<"entrer le nom du "<<i<<" etat";
cin>>p.inf;
cout<<"entrer le nombre de derivation de l etat "<<p.inf<<" :";
cin>>n;
z=cree_list_derivation(p,n);
// p->deriv_suiv=z->deriv_suiv;
for(i=2;i<=x;i++)
{
// q=new(etat);
// p->etat_suiv=q->etat_suiv;
cout<<"entrer le nom du "<<i<<" etat";cin>>q.inf;
cout<<"entrer le nombre de derivation de l etat "<<q.inf<<" :";
cin>>n;
a=cree_list_derivation(q,n);
// q->deriv_suiv=a->deriv_suiv
p=q;
}
//p->etat_suiv=NULL;
return (g);
}
/*********************************************************************************/
/*on definit une fonction qui teste l'existance d'un carectere dans la liste intermidiare*/
/************************************************************************************/
bool existance(element L,char c)
{ element p;
p=L;
bool trouve;
while((p !=NULL)&&(trouve=false))
{ if(p.information==c)
{ trouve=true;
p=p.suivant;
}
return(trouve);
}
/*********************************************************************************/
/**=======declaration de la fonction ajouter qui va etre utilisée dans la fonction de determinisation*/
/*********************************************************************************************/
etat ajoute_etat(etat g,char c)
{etat p;
etat s;
p=g;
while (p!=NULL)
{ p=p.etat_suiv;
}
// NE=new(etat);
NE.inf=c;
NE.etat_sui=NULL;
NE.deriv_suiv=NULL;
p.etat_suiv=NE;
return(NE);
}
/*****************************************************************/
/**********declaration de la fonction ajouter qui prend la liste des derivation et le nom de l'etat*
/***a deriver et rendre la tete de la liste .permet d'inserer tout les voisins de meme alphabet *
/*********elle est de type graph***************************************************/
graph ajouter(graph E,char k,char d)
{ graph s;
s=new(graph);
s.info=k // ici par exemple le nom de l'atat s1
s.arc=d //ici par exemple le carectere a
E.suivant=s;
return(E);
}
/****************************************************************/
/*declaration de la fonction chercher qui va etre utiliser dand la fonction inserer*/
/*********************************************************************/
etat et;
etat chercher_etat(char eta,etat r)
{//et=new(etat);
while(r.info != NULL)
{
if(r.info==eta)
{
et=r;
}
r=r->et_suiv;
}
return (et);
}
/**********************************************************************************************/
/****declaration de la fonction inserer de type etat qui permet d'inserer la liste des voisins
/***********************************************************************************************/
//**** aprés qu'on trouve un etet nom deterministe ça veut dire qu'il a 02 transition avec le meme alphabet******
//on doit ajouter un nouvel etat qui porte le nom de ses 02 etat en plus on doit chercher pour
//chaque etat sa liste de derivations avec le meme alphabet et puis concatiner ces 02 listes
//********************************************************************************* //
etat U;
char n;
derivation p1;
derivation s;
derivation k;
derivation v;
k=new(derivation);
derivation inserer(derivation NE,graph E)
{
k->val=n;
v=k;
while(E != NULL)
{
U=chercher_etat(etat G,E->info);
p1=U.deriv_suiv;
while(p1 != NULL)
{ if (p1.val==E->arc)
{ s=new(derivation);
s.val=p1->val;
s.carectere=p1->carectere;
s.final=p1->final;
v.deriv_voisin=s;
s=v;
}
p1=p1.deriv_voisin;
}
E=E.suivant;
}
v.deriv-voisin=NULL;
return(k);
}
/**********************************************************************/
//--------------------*////fonction de determination===============**/
/*******************************************************************/
etat determ_aut(etat G)
{etat NE;
graph E;
derivation p;
derivation p1;
derivation s;
derivation ND;
bool TEF;
while(G !=NULL) // la boucle qui parcours les etats
{ p=G.deriv_suiv; // passer à la liste des derivations
s=p.deriv_voisin;
int nbr=0; //un compteur qui compte le nbr des deriavtions d'un alphabet
while(s !=NULL) // pour connaitre les alphabets qui ont au plus d'une derivation
{ if(s.carectere==p.carectere)
nbr++;
s=s.deriv_voisin;
}
if (nbr>1)//p a plusieurs derivation avec le meme alphabet
{
new(E);
p1=p; // sauvegarder le précédent pour faciliter la suppression
E.suivant=NULL;
E.info=p->val;
E.arc=p->carectere;
TEF=p->final;
p=p.deriv_voisin;
while(p !=NULL)
{
if(p.val=E.arc)// on a trouvé une nouvelle derivation de cet alphabet
{ E=ajouter(E,p->carectere,p.val)
s=p.deriv_voisin;
delete(p);
p1.deriv_voisin=s;
TEF=p.final;
}
p=p.deriv_voisin;
p1=p1.deriv_voisin;
}
// new(ND);
p1.deriv_voisin=NULL;
ND.deriv_voisin=NULL;
ND.final=TEF;
ND.carectere=E->arc;
cout<<"lire le nom de nouveau etat"<<endl;
NE=ajouter_etat(G,ND->val);
NE.deriv_voisin=inserer(NE,E);
derivation I;
derivation w;
I=NE.deriv_suiv;
w=I.deriv_voisin;
delete(I);
NE.deriv_voisin=W;
}
G=G.etat_suiv;
return(G)
}
/****************************************************************************/
/********************fonction d'affichage de l'automate*********************/
/*************************************************************************/
void affiche_aut(etat g)
{ derivation s;
etat p=g;int i=0;
cout<<"on va afficher etat par etat dans chaque etat on doit present ses derivation"<<endl;
while (p!=NULL)
{
i=i+1;
cout<<"le "<<i<<"etat est <<p.nom<<endl";
s=p->deriv_suiv;
while (s!=NULL)
{
cout<<"l etat"<<p.inf<<"produit un "<<s.carectere<<"et passe vers l etat"<<s.val<<endl;
s=s.deriv_voisin;
}
cout<<"c fini pour l etat "<<p->inf<<"on passe au etat suivant"<<endl;
p=p->etat_suiv;
}
}
/************************************************************************************/
/*on definit la fonction qui teste si l'automate est deterministe ou non */
/*en utilisant les fonctions que nous avons déclmarer precedemernt*/
/*********************************************************************/
bool TESTE_D(etat G)
{ bool nondeterminste;
derivation k;
bool boole;
element p2;
element tete;
element li;
element F;
while(G<>NULL)&&(nondeterministe=false)
{ k=G.derivation;
boole=true;
new(li);
li.inf=k->carectere ;
tete=li;
while(k<>NULL)&&(boole)
{ existance(li,k.carectere);
if(trouve=true)
{
boole=false;
printf("automate non deterministe");
nondeterministe=true;
determ_aut(G);
}
else
{ new(F);
F.inf=k.caretere;
li.suiv=F;
F=li;
}
k=k.deriv_suiv;
}
/**********************************/
/*on libere maintenant la liste intermidiare*/
while (li<>NULL)
{
p2=tete.suivant;
delete(tete);
tete=p2;
}
G=G.etat_suiv ;
}
return(nondeterminste);
}
/*************************************************************/
//==============programme principal================================================//
/*&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&*/
int main()
{ int x;
cout<<"entrer le nombre des etats dans l'automate: ";
cin>>x;
etat automate=cree_list_etat(x);