Transformation afn en afd

Commenter

Contenu du snippet

pour ceux qui cherche un programme qui transforme un afn en afd

Source / Exemple : 


///////////////////////////////////////////////////////////////////////////
// Transformation AFN en AFD
//
#include <stdio.h>
#include <stdlib.h>

///////////////////////////////////////////////////////////////////////////
//
//
#define EPSILON		-1
#define NOETAT		-1

///////////////////////////////////////////////////////////////////////////
// A F N
//
typedef struct ptr_list* ptr_list_t;
struct ptr_list
{
	int        info;
	ptr_list_t suiv;
};

typedef struct ptr_trans* ptr_trans_t;
struct ptr_trans
{
	int		    e, s;
	ptr_list_t	vers_e;
	ptr_trans_t suiv;
};

typedef struct
{
	ptr_list_t	letat;
	ptr_list_t	lsymb;
	ptr_trans_t	ltrans;
}afn_t;

///////////////////////////////////////////////////////////////////////////
// A F D
//
typedef struct ptr_detat* ptr_detat_t;
struct ptr_detat
{
	int			e;
	ptr_list_t	letat;
	ptr_detat_t suiv;
};

typedef struct ptr_dtrans* ptr_dtrans_t;
struct ptr_dtrans
{
	int			 de, s, fe;
	ptr_dtrans_t suiv;
};

typedef struct
{
	ptr_detat_t	 ldetat;
	ptr_list_t	 lsymb;
	ptr_dtrans_t ltrans;
}afd_t;

///////////////////////////////////////////////////////////////////////////
// P R O T O T Y P E
//
afn_t* saisie_afn();
void   affiche_afd(afd_t*);
afd_t* afn2afd(afn_t*);
void   free_afn(afn_t*);
void   free_afd(afd_t*);

///////////////////////////////////////////////////////////////////////////
// F O N C T I O N   M A I N
//
void main()
{
	// Variables locales
	afn_t *afn;
	afd_t *afd;

	// Création de l'AFN
	afn = saisie_afn();

	// Transformation de l'AFN
	afd = afn2afd(afn);

	// Affichage des resultats
	affiche_afd(afd);

	// Libération de la mémoire
	free_afn(afn);
	free_afd(afd);
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_list(ptr_list_t p)
{
	while (p)
	{
		ptr_list_t q = p;
		p = p->suiv;
		free(q);
	}
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_afn(afn_t *afn)
{
	ptr_trans_t q, p = afn->ltrans;

	free_list(afn->letat);
	free_list(afn->lsymb);
	while (p)
	{
		q = p;
		p = q->suiv;
		free_list(q->vers_e);
		free(q);
	}
}

///////////////////////////////////////////////////////////////////////////
//
//
void free_afd(afd_t *afd)
{
	ptr_detat_t  q1, p1 = afd->ldetat;
	ptr_dtrans_t q2, p2 = afd->ltrans;
	while (p1)
	{
		q1 = p1;
		p1 = q1->suiv;
		free_list(q1->letat);
		free(q1);
	}
	free_list(afd->lsymb);
	while (p2)
	{
		q2 = p2;
		p2 = p2->suiv;
		free(q2);
	}
}

///////////////////////////////////////////////////////////////////////////
// 
//
void list_inserer(ptr_list_t *ptr, int e)
{
	ptr_list_t p = (ptr_list_t)malloc(sizeof(struct ptr_list));
	p->info = e;
	p->suiv = 0;
	if (*ptr)
	{
		ptr_list_t q;
		for (q = *ptr; q->suiv; q = q->suiv);
		q->suiv = p;
	}
	else


    		
  • ptr = p;

}

///////////////////////////////////////////////////////////////////////////
//
//
afn_t* saisie_afn()
{
	int         nbr_etat, nbr_symb, nbr, i, j, k, e;
	afn_t       *afn;
	ptr_trans_t	tr;

	afn = (afn_t*)malloc(sizeof(afn_t));
	afn->letat  = 0;
	afn->lsymb  = 0;
	afn->ltrans = 0;

	// La list des etats
	printf("Donner le nombre des etats: ");
	scanf("%d", &nbr_etat);
	for (i = 0; i < nbr_etat; i++)
		list_inserer(&afn->letat, i);

	/* La list des symboles */
	printf("Donner le nombre des symboles (sans compter l'epsilon): ");
	scanf("%d", &nbr_symb);
	for (i = 0; i < nbr_symb; i++)
		list_inserer(&afn->lsymb, i);

	// La list des transition
	for (i = 0; i < nbr_etat; i++)
		for (j = -1; j < nbr_symb; j++)
		{
			if (j == -1)
				printf("De l'etat '%d' combien d'etat vous pouvez atteindre avec le symbole epsilon: ", i);
			else
				printf("De l'etat '%d' combien d'etat vous pouvez atteindre avec le symbole %c: ", i, 'a' + j);

			scanf("%d", &nbr);
			if (nbr)
			{
				tr = (ptr_trans_t)malloc(sizeof(struct ptr_trans));

				tr->e      = i;
				tr->s      = j;
				tr->vers_e = 0;

				for (k = 0; k < nbr; k++)
				{
					printf("Vous pouvez atteindre l'etat ? ");
					scanf("%d", &e);
					list_inserer(&tr->vers_e, e);
				}

				tr->suiv    = afn->ltrans;
				afn->ltrans = tr;
			}
		}

	return (afn);
}

///////////////////////////////////////////////////////////////////////////
//
//
void affiche_afd(afd_t *afd)
{
	ptr_detat_t d;
	ptr_list_t  s;

	d = afd->ldetat;
	printf("  |");
	for (s = afd->lsymb; s; s = s->suiv)
		printf(" %c |", 'a' + s->info);
	printf("\n");
	for (d = afd->ldetat; d; d = d->suiv)
	{
		ptr_dtrans_t ldtr;

		printf("%c |", 'A' + d->e);
		for (ldtr = afd->ltrans; ldtr; ldtr = ldtr->suiv)
			if (ldtr->de == d->e)
				printf(" %c |", 'A' + ldtr->fe);
		printf("\n");
	}
}

///////////////////////////////////////////////////////////////////////////
//
//
void afd_ajouter_etat(ptr_detat_t *ldetat, int e, ptr_list_t letat)
{
	ptr_detat_t lde;
	ptr_list_t  p;

	lde = (ptr_detat_t)malloc(sizeof(struct ptr_detat));

	lde->e     = e;
	lde->letat = 0;
	lde->suiv  = 0;
	for (p = letat; p; p = p->suiv)
		list_inserer(&lde->letat, p->info);

	if (*ldetat)
	{
		ptr_detat_t q;
		for (q = *ldetat; q->suiv; q = q->suiv);
		q->suiv = lde;
	}
	else


    		
  • ldetat = lde;

}

///////////////////////////////////////////////////////////////////////////
//
//
int is_in_list(ptr_list_t letat, int e)
{
	ptr_list_t p;
	for (p = letat; p; p = p->suiv)
		if (p->info == e)
			return (1);
	return (0);
}

///////////////////////////////////////////////////////////////////////////
//
//
int epsilon_arc(afn_t* afn, int se, int fe)
{
	ptr_trans_t p;
	ptr_list_t  q;
	for (p = afn->ltrans; p; p = p->suiv)
		if ((p->e == se) && (p->s == EPSILON))
			for (q = p->vers_e; q; q = q->suiv)
				if (q->info == fe)
					return (1);
	return (0);
}

///////////////////////////////////////////////////////////////////////////
//
//
void empiler_etat(ptr_list_t *p, int e)
{
	ptr_list_t q = (ptr_list_t)malloc(sizeof(struct ptr_list));
	q->info = e;
	q->suiv = *p;


    	
  • p      = q;

}

///////////////////////////////////////////////////////////////////////////
//
//
int depiler_etat(ptr_list_t *letat)
{
	int e;
	ptr_list_t p;

	if (*letat)
	{
		e      = (*letat)->info;
		p      = *letat;


    		
  • letat = p->suiv;

		free(p);
		return (e);
	}
	else
		return (NOETAT);
}

///////////////////////////////////////////////////////////////////////////
//
//
ptr_list_t epsilon_fermeture(afn_t* afn, ptr_list_t T)
{
	ptr_list_t p, e_f = 0, pile_etat = 0;
	int t;

	for (p = T; p; p = p->suiv)
	{
		/* On initialise le epsilon fermeture de T à T */
		list_inserer(&e_f, p->info);
		/* On empile tout les etats des T */
		empiler_etat(&pile_etat, p->info);
	}

	/* Tant que pile est non vide */
	while ((t = depiler_etat(&pile_etat)) != NOETAT)
	{
		for (p = afn->letat; p; p = p->suiv)
		{
			/* Pour chaque etat u avec un arc de t à u etiquite epsilon */
			/* u = p->e*/
			if (epsilon_arc(afn, t, p->info))
			{
				/* Si u n'appartient pas à epsilon fermeture de T */
				if (!is_in_list(e_f, p->info))
				{
					/* Ajouter u à l'epsilon fermeture de T */
					list_inserer(&e_f, p->info);
					/* On empile u dans la pile */
					empiler_etat(&pile_etat, p->info);
				}
			}
		}
	}
	return (e_f);
}

///////////////////////////////////////////////////////////////////////////
//
//
void afd_ajouter_trans(ptr_dtrans_t *ltrans, int de, int fe, int s)
{
	ptr_dtrans_t dtrans = (ptr_dtrans_t)malloc(sizeof(struct ptr_dtrans));
	dtrans->de   = de;
	dtrans->fe   = fe;
	dtrans->s    = s;
	dtrans->suiv = 0;

	if (*ltrans)
	{
		ptr_dtrans_t q;
		for (q = *ltrans; q->suiv; q = q->suiv);
		q->suiv = dtrans;
	}
	else


    		
  • ltrans = dtrans;

}

///////////////////////////////////////////////////////////////////////////
//
//
int afd_trouve_etat(afd_t *afd, ptr_list_t letat)
{
	ptr_detat_t dp;
	ptr_list_t  dp_le, dp_e;

	for (dp = afd->ldetat; dp; dp = dp->suiv)
	{
		int nbr_element = 0;

		/* Sont t-il egaux en nombre d'element */
		for (dp_e = dp->letat; dp_e; dp_e = dp_e->suiv, nbr_element++);
		for (dp_le = letat; dp_le; dp_le = dp_le->suiv, nbr_element--);
		if (nbr_element == 0)
		{
			for (dp_e = dp->letat; dp_e; dp_e = dp_e->suiv)
			{
				int trouve = 0;

				for (dp_le = letat; dp_le; dp_le = dp_le->suiv)
					if (dp_le->info == dp_e->info)
					{
						trouve = 1;
						break;
					}
				if (trouve == 0)
					return (NOETAT);
			}
			return (dp->e);
		}
	}
	return (NOETAT);
}

///////////////////////////////////////////////////////////////////////////
//
//
ptr_list_t transiter(afn_t* afn, ptr_list_t letat, int s)
{
	ptr_list_t  p, q, tran = 0;
	ptr_trans_t tr;

	for (p = letat; p; p = p->suiv)
		for (tr = afn->ltrans; tr; tr = tr->suiv)
			if ((tr->e == p->info) && (tr->s == s))
				for (q = tr->vers_e; q; q = q->suiv)
					list_inserer(&tran, q->info);

	return (tran);
}

///////////////////////////////////////////////////////////////////////////
//
//
afd_t* afn2afd(afn_t *afn)
{
	afd_t      *afd;
	ptr_list_t  L = 0, U, s;
	ptr_detat_t p;
	int         ee, e = 0;

	afd = (afd_t*)malloc(sizeof(afd_t));
	afd->ldetat = 0;
	afd->lsymb  = 0;
	afd->ltrans = 0;

	/* L'AFN et l'AFD ont les même symboles */
	for (s = afn->lsymb; s; s = s->suiv)
		list_inserer(&afd->lsymb, s->info);

	list_inserer(&L, 0);
	U = epsilon_fermeture(afn, L);
	afd_ajouter_etat(&afd->ldetat, e++, U);
	for (p = afd->ldetat; p; p = p->suiv)
	{
		for (s = afn->lsymb; s; s = s->suiv)
		{
			/* Netoyage de mémoire */
			free_list(L);
			free_list(U);

			L = transiter(afn, p->letat, s->info); 
			U = epsilon_fermeture(afn, L);

			ee = afd_trouve_etat(afd, U);
			if (ee == NOETAT)
			{
				/* On lui donne un nom */
				ee = e++;
				afd_ajouter_etat(&afd->ldetat, ee, U);
			}
			afd_ajouter_trans(&afd->ltrans, p->e, ee, s->info);
		}
	}
	free_list(L);
	free_list(U);

	return (afd);
}

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.

Du même auteur (cs_mido123)