TRANSFORMATION AFN EN AFD

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