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


/* Cvor liste u kojoj se cuvaju kodirani skupovi stanja 
   i njihove odgovarajuce celobrojne oznake. Iako lista nije
   najefikasnija struktura za ovu potrebu, ovde se koristi zbog 
   citljivosti i lakseg razumevanja koda. Takodje, nije vrsena nikakva
   kompakcija tablica prelaska, tako da se ovaj kod ne moze smatrati 
   optimalnim */
typedef struct _Cvor
{   unsigned long skup_stanja;
    unsigned long nova_oznaka;
	struct _Cvor *sledeci;
} CVOR;

/* Ideja je da se skup stanja predstavi kao jedan unsigned long.
   Odgovarajuci bit tog broja je setovan ukoliko se stanje nalazi u skupu */
struct NKA
{   /* Skup zavrsnih stanja */
	unsigned long zavrsna;
	/* Skup pocetnih stanja */
    unsigned long pocetna;
	/* Tablice prelaska */
	unsigned long prelaz[26][32];
};


/* Posto broj stanja ovde nije ogranicen, koristi se dinamicka struktura */
struct DKA
{   /* Broj stanja i tablica prelaska */
	unsigned long br_stanja;
	unsigned long **prelaz;

	/* Broj zavrsnih stanja i niz zavrsnih stanja */
    unsigned long br_zavrsnih;
    unsigned long *zavrsna;   
};

/* Funkcija ubacuje vec izgradjenu vrstu p koja predstavalja tablice prelaska 
   za stanje os u automat D. Ukoliko je fleg zavrsno postavljen, stanje os se dodaje
   u spisak zavrsnih stanja */
void UbaciStanje(struct DKA* D, unsigned long* p, unsigned long os, int zavrsno)
{	unsigned long i;
    /* Ukoliko nije alocirano dovoljno memorije, vrsi se realokacija niza */
	if (os>D->br_stanja)
	{	unsigned long **np;
		np=(unsigned long**)malloc(os*sizeof(unsigned long*));
		for (i=0; i<D->br_stanja; i++)
			np[i]=D->prelaz[i];
		
		D->br_stanja=os;
		D->prelaz=np;
	}
	
	/* Posto indeksi niza pocinju od 0, a stanja od 1, vrsta se ubacuje na mesto 
	   os-1 */
	D->prelaz[os-1]=p;

	/* Ukoliko je fleg zavrsno postavljen, stanje os se dodaje
	   u realocirani spisak zavrsnih stanja */
	if (zavrsno)
	{  unsigned long* nz=(unsigned long*)malloc((++(D->br_zavrsnih))*sizeof(unsigned long));
	   for (i=0; i<D->br_zavrsnih-1; i++)
		   nz[i]=D->zavrsna[i];
	   nz[D->br_zavrsnih-1]=os;
	   D->zavrsna=nz;
	}
}

/* Funkcija u listu d pokusava da ubaci skup stanja ss i postavi oznaku 
   tog skupa stanja na no. Ukoliko stanje vec postoji, funkcija ne vrsi nikakvo 
   ubacivanje vec vraca ranije postavljenu oznaku tog skupa stanja. Ubacivanje 
   se vrsi u uredjenu listu */
int Ubaci(CVOR **d, unsigned long ss, unsigned long no)
{	if ((*d)==NULL)
	{	(*d)=(CVOR *)malloc(sizeof(CVOR));
		(*d)->skup_stanja=ss;
		(*d)->nova_oznaka=no;
		(*d)->sledeci=NULL;
		return no;
	}
    
	if ((*d)->skup_stanja<ss) 
		return Ubaci(&(*d)->sledeci,ss,no);
	
	if((*d)->skup_stanja>ss) 
	{	CVOR* pom=(CVOR *)malloc(sizeof(CVOR));
	    pom->sledeci=(*d)->sledeci;
		pom->skup_stanja=(*d)->skup_stanja;
		pom->nova_oznaka=(*d)->nova_oznaka;
		(*d)->skup_stanja=ss;
		(*d)->nova_oznaka=no;
		return no;
	}

    return (*d)->nova_oznaka;
}


/* Funkcija pokusava da pronadje oznaku skupa stanja ss u listi 
   c. Ukoliko skup stanja ne postoji, funkcija vraca 0 */
unsigned long Pronadji(CVOR *c, unsigned long ss)
{	if (c==NULL) return 0;
	if (c->skup_stanja==ss) return c->nova_oznaka;
	if (c->skup_stanja<ss)  return Pronadji(c->sledeci,ss);
	return 0;
}


void Determinizuj(struct NKA* Nedet, struct DKA* Det)
{  	/* lista stanja deterministickog automata koja su obradjena, 
	   tj. ciji su prelazi odredjeni */
	CVOR *obradjena=NULL;
     
	/* lista stanja deterministickog automata koja jos nisu obradjena */
    CVOR *neobradjena=NULL; 

	/* Oznaka sledeceg stanja deterministickog automata */
	unsigned long tekuca_oznaka=1;
   
	/* Deterministicki automat postavljamo na "prazan"*/
	Det->br_stanja=0;
	Det->br_zavrsnih=0;

	/* Pocetna stanja nedeterministickog automata ubacujemo u listu 
	   neobradjenih stanja. Ona cine jedinstveno pocetno stanje 
	   deterministickog automata */
	Ubaci(&neobradjena,Nedet->pocetna,tekuca_oznaka++);

	/* Sve dok ima jos neobradjenih stanja */
	while (neobradjena!=NULL)
	{	int i,j;
		unsigned long *pr;
		
		/* Uzimamo prvo neobradjeno stanje, prebacujemo ga u obradjena i
		   dalje vrsimo njegovu obradu*/
		CVOR *tekuci_skup=neobradjena;
		neobradjena=neobradjena->sledeci;
		Ubaci(&obradjena,tekuci_skup->skup_stanja,tekuci_skup->nova_oznaka);

		/* Vrsta u tablici prelaska deterministickog automata koja odgovara 
		   stanju koje upravo obradjujemo */
		pr=(unsigned long*)malloc(26*sizeof(unsigned long));

		/* Za svako slovo azbuke */
		for (i=0; i<26; i++)
		{	/* Skup stanja u koje se moze stici ako se krene iz nekog od 
			   stanja skupa koji trenutno obradjujemo preko tekuceg slova */
			unsigned long prelaz=0;

			/* Dekodiramo long koji cuva skup stanja i odredjujemo prelaz */
			for (j=0; j<32; j++)
			{	/* Konjunkcijom odredjujemo da li je j-ti bit setovan,
				   sto znaci da tekuci skup stanja sadrzi stanje j
				   nedetrministickog automata */
				if ((tekuci_skup->skup_stanja)&(1<<j))
					/* Disjunkcijom dodajemo u skup stanja prelaz
					   sva stanja nedeterministickog automata u koje se
					   moze stici iz stanja j preko slova i*/
					prelaz|=Nedet->prelaz[i][j];
			}

			/* Ako postoji prelaz utvrdjujemo da li smo se ranije susretali 
			   sa tim skupom stanja */
			if (prelaz)
			{	unsigned long no=Pronadji(obradjena,prelaz);
			    /* Ako skup stanja prelaz postoji vec u listi obradjenih, no ce da 
				   sadrzi odgovarajucu oznaku stanja deterministickog automata != 0*/
				if (no==0)
				{   /* Pokusavamo da ubacimo skup stanja prelaz u listu neobradjenih.
					   Ako vec postoji rezultat no je oznaka odgovarajuceg stanja 
					   deterministickog automata */
					if ((no=Ubaci(&neobradjena,prelaz,tekuca_oznaka))==tekuca_oznaka)
						tekuca_oznaka++;   
				}
                
				/* Postavljamo odgovarajuci element tablice prelaska deterministickog automata */
				pr[i]=no;
			} 
			else 
				pr[i]=0; /* 0 oznacava da prelaz ne postoji */
		}
		
		/* Izgradjenu vrstu ubacujemo u tablice prelaska i uz to odredjujemo da li je stanje zavrsno */
		UbaciStanje(Det,pr,tekuci_skup->nova_oznaka,tekuci_skup->skup_stanja&Nedet->zavrsna);
	}
}



/* Pomocna funkija koja ispisuje deterministicki automat */
void IspisiAutomat(struct DKA* D)
{  unsigned long i,j;
   for (i=0; i<D->br_stanja; i++)
	   for (j=0; j<26; j++)
			if (D->prelaz[i][j])
				printf("prelaz[%u][%c]=%u\n",i+1,j+'a',D->prelaz[i][j]);
   printf("Zavrsna stanja : ");
   for (i=0; i<D->br_zavrsnih; i++)
	   printf("%u   ",D->zavrsna[i]);
}


/* Test primer. Automat prihvata (a|b)*abb */
main()
{   struct NKA N;
	struct DKA D;
	int i,j;

	N.pocetna=1;
	N.zavrsna=8;
	N.prelaz[0][0]=3;
	N.prelaz[0][1]=0;
	N.prelaz[0][2]=0;
	N.prelaz[1][0]=1;
	N.prelaz[1][1]=4;
	N.prelaz[1][2]=8;
    for (i=3; i<32; i++)
	{ N.prelaz[0][i]=0;
	  N.prelaz[1][i]=0;
	}
	for (i=2; i<26; i++)
		for (j=0;j<32; j++)
		   N.prelaz[i][j]=0;

    Determinizuj(&N,&D);
	IspisiAutomat(&D);

	return 0;
}