Construction d'une automate finis deterministe

Soyez le premier à donner votre avis sur cette source.

Snippet vu 17 990 fois - Téléchargée 19 fois

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

Ajouter un commentaire

Commentaires

Pourriez vous donner des exemples de données valides en entrée
Messages postés
4
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
28 mars 2010

@ Clio908
salut pour la bonne utilisation de ce code il faut que
*Les transitions soit des lettres (a..z & A..Z & 1..9)
*les états initiaux et finaux sont des entiers.
*pour taper un mot , il faut tout d'abord donner le nb des lettres puis chaque lettre à part.
*Faites bien attention pour les msg que le programme te donne (exemple Voulez vous ajouter d'autres transitions ?) pour ne pas se tromper
et en plus essayer de l'exécuter sous le microsoft studio ou bien geany , je te garantie ça marche :)
@+
Messages postés
15
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
21 novembre 2010

pour le while j'ai pigé...
pour l'utiliser pas encore!
Messages postés
15
Date d'inscription
samedi 22 décembre 2007
Statut
Membre
Dernière intervention
21 novembre 2010

Bonjour
J'essaie de le faire tourner sur code:block mais pb
Pourriez vous donner des exemples de données valides en entrée (transitions...)
De plus je comprends pas après un while, y faut pas des op entre { et }?
...
while ((v!=1)&&( ptrcombo!=NULL));
if (ptrcombo==NULL) trouv=5;
...
merci
Messages postés
4
Date d'inscription
mercredi 30 décembre 2009
Statut
Membre
Dernière intervention
28 mars 2010

plutot c kelkin qui veut gagner du bonus pour ameliorer son note de DS :D
Wow Mon 1er commentaire :)
Merci FretMan92
Afficher les 7 commentaires

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.