Construction d'une automate finis deterministe

Commenter

Contenu du snippet

avec mon programme, vous pouvez construire une automate finis deterministe et meme essayer quelques mot pour savoir est ce qu'ils appartienne a son langage ou nn.

Source / Exemple : 


//      AFD.cpp
//      Copyright 2010 Bilel <skible@skible-laptop>
//      
//      This program is free software; you can redistribute it and/or modify
//      it under the terms of Mr Msekni Bilel.
//      
//      This program is distributed in the hope that it will be useful,
//      but WITHOUT ANY WARRANTY; without even the implied warranty of
//      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//      GNU General Public License for more details.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct etat
			{ 
				int init;
				int fini;
				etat *succ;
			}; 
struct combo
		{
			char transition[2];
			etat *tete_etat;
			combo *succ; 
		};
		typedef combo* COMBO;
		typedef etat* ETAT;

	COMBO construire()
	{
		//Ici on fait la construction de notre automate.
	
		int replicate(ETAT tete_etat,int init,ETAT tete_combo);
		char condition1 [4],condition2 [4];
		combo* tete_combo=NULL;
		combo *p_combo;
		etat *p_etat;
		combo* suiv=NULL;
		etat* ref=NULL;
		int l=0;
	
		do
		{
			p_combo= (combo*)malloc(sizeof (combo));
		
		printf("Donnez une transition\n");
		scanf("%s",(*p_combo).transition);
		if (tete_combo==NULL) p_combo->tete_etat=NULL;
		else{ p_combo->tete_etat=tete_combo->tete_etat;
		ref=tete_combo->tete_etat;
		}
			do
			{
				p_etat=(etat*)malloc(sizeof (etat));
				
				do
				{
			printf("Donnez etat initial\n");
			scanf("%i",&(*p_etat).init);
			 
			l=replicate(p_combo->tete_etat,p_etat->init,ref);
			if (l==1) printf("ERREUR, Il existe deja une transition commencant de cette etat init\n");
				}
				while(l!=0);
			printf("Donnez etat final\n");
			scanf("%i",&(*p_etat).fini);
			p_etat->succ=p_combo->tete_etat;
				(*p_combo).tete_etat=p_etat;
			printf("Voulez vous ajouter d'autres etats pour cette transition ? (oui/non)\n");
			scanf("%s",condition1);
			l=strcmp(condition1,"non");
		    }
			while (l!=0);
			(*p_combo).succ=tete_combo;
				tete_combo=p_combo;
				
			printf("Voulez vous ajouter d'autres transitions ? (oui/non)\n");
			scanf("%s",condition2);
			l=strcmp(condition2,"non");
			
		}
			while(l!=0);
			p_combo=tete_combo;
			
		do
		{
			suiv=p_combo->succ;
			
			do
			{
				printf("%s\t",p_combo->transition);
				printf("%i\t",p_etat->init);
				printf("%i\t",p_etat->fini);
				printf("\n");
				p_etat=p_etat->succ;
				if ((suiv==NULL)||(p_etat != suiv->tete_etat)) l=1;
				else l=0;
			}
			while ((p_etat!= NULL) &&  l!=0);
		p_combo=p_combo->succ;
		
		} while (p_etat != NULL);
		return (COMBO)tete_combo;
	}
		int replicate(etat *tete_etat,int init,etat* ref)
		{// Ici on verifie est ce que une transition a une etat initiale identique à celui qu'on a juste tapez.
			int replicate=0;

			while ((tete_etat!=NULL) && (replicate==0) && (tete_etat!=ref))
			
			{
				if (tete_etat->init ==init) replicate=1;
				else tete_etat=tete_etat->succ;
			}

			return replicate;
		}
		char* mot()
		{
			//Ici se fait la construction du mot qu'on va vérifier avec l'AFD.
			int nb,i;
			char *tab;
			printf("Donnez la taille du mot\n");
			scanf("%d",&nb);
			tab= (char *) malloc((nb+1)*sizeof(char));
			
			for(i=0;i<nb;i++)
			{
				printf("Donner la lettre %d\n",i+1);
				scanf("%s",&tab[i]);
			}
			tab[nb]='\0';
			return &tab[0];
			
		}
		char check(char* adrtab,COMBO adrcombo)
		{
			int res=0,trouv=1,i=0;
			//Ici on vérifie l'appartenance du notre mot au language de notre automate.
			int etatinit,v=0;
			combo *ptrcombo=adrcombo;
			etat *ptretat;
			etat *ref=NULL;
			
			printf("Donner etat de depart\n");
			scanf("%i",&etatinit);
			
		
				while (res==0 && trouv==1)
			{    
				  do
				  {
				  if ((*ptrcombo).transition[0]==adrtab[i]) {v=1;
															ptretat=ptrcombo->tete_etat;
															if (ptrcombo->succ != NULL)
															ref=(*ptrcombo).succ->tete_etat;
															}
				else ptrcombo=(*ptrcombo).succ;
				
			}
			
				while ((v!=1)&&( ptrcombo!=NULL));
				if (ptrcombo==NULL) trouv=5;
				else
				{
					i++;	
					   do
				if ((*ptretat).init==etatinit) {v=2;
												etatinit=(*ptretat).fini;
											}
				else ptretat=(*ptretat).succ;
				while ((v!=2)&&( ptretat!=NULL)&&( ptretat!=ref));
				if ((ptretat==NULL)||( ptretat==ref)) trouv=0;
				else 	
		           if (adrtab[i]=='\0') res=1;
		           ptrcombo=adrcombo;
			   }
			   
		   }
		  
		
		  if (res==1) return etatinit;
		  else {
			  printf("Mot rejeté\n");
			  return -1;
		  }
	   }
		int main()
		{
			//C'est la fonction main.
			char rep[3];
			int final[1],i,nb;
			COMBO k=construire();
			do
			{
			char* tab=mot();
			printf("Votre mot est %s. On va la tester maintenant :D !!!\n",tab);
			int s = check(tab,k);
			if (s!=-1)
			{
				printf("Donnez le nombre des etats finaux\n");
				scanf("%i",&nb);
			for(i=0;i<nb;i++)
			{
				printf("Donnez etat final %i\n",i+1);
				scanf("%i",&final[i]);
			}
			
			do
			{
				i--;
				if (s==final[i]) printf("Mot Accepte\n");
			}
			while ((i>=0)&&(s!=final[i]));
			if (i<0) printf("\nMot rejete");
		}
		printf("Voulez vous essayez un autre mot ? (oui/non)\n");
		scanf("%s",rep);
	}
		while(strcmp(rep,"non")!=0);
			return 0;
		}

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.