CONSTRUCTION D'UNE AUTOMATE FINIS DETERMINISTE

//      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;
		}