NFA TO DFA

KERALA UNIVERSITY COMPUTER SCIENCE LAB PPROGRAMS

NFA TO DFA CONVERSTION

#include
#include
#include
#include
char nttable[30][30][10],dttable[30][30][10];
int stack[30],top=-1;
struct node
{
int a;
node *link;
};
node *top1=NULL;
int *eclosure(int start,int end)
{
int *closure=NULL;
closure=new int[20];
for(int i=0;i<20;i++)
closure[i]=44;
if(top==-1)
return(NULL);
while(top!=-1)
{
closure[stack[top]]=stack[top];
for(int i=start;i<=end;i++)
{
if(strchr(nttable[stack[top]][i],'e')!=NULL)
{
if(closure[i]==44)
{
top++;
stack[top]=i;
closure[i]=i;
i=start;
}
}
}
top--;
}
return(closure);
}
void findtransition(char a,int b,int start,int end)
{
for(int i=start;i<=end;i++)
{
if(strchr(nttable[b][i],a)!=NULL)
{
top++;
stack[top]=i;
}
}
return;
}
int newstate(int *closure,int *news[30],int nostates)
{
int x;
for(int i=0;i<=nostates;i++)
{
x=0;
for(int j=0;j<20;j++)
{
if(closure[j]!=44)
{
if(closure[j]!=news[i][j])
{
x=1;
j=21;
}
}
}
if(x==0)
return(i);
}
return(-1);
}
void main()
{
clrscr();
fstream p;
char inchar[30];
int start,sstate,estate,end,*news[30],nostates=-1;
char in[30];
cout<<"Enter input characters: ";
cin>>inchar;
p.open("input.txt",ios::in);
p>>start>>end;
do
{
p>>sstate>>estate>>in;
strcat(nttable[sstate][estate],in);
} while(p.eof()!=1);
int *closure;
top++;
stack[top]=start;
closure=eclosure(start,end);
news[++nostates]=closure;
node *temp=new node;
temp->a=nostates;
temp->link=top1;
top1=temp;
int d,yes,g;
cout<<"start end transition";
while(top1!=NULL)
{
d=top1->a;
top1=top1->link;
for(int i=0;i<20;i++)
{
if(news[d][i]!=44)
{
for(int j=0;inchar[j]!='\0';j++)
{
findtransition(inchar[j],news[d][i],start,end);
closure=eclosure(start,end);
if(closure!=NULL)
{

yes=newstate(closure,news,nostates);
g=yes;
if(yes==-1)
{
nostates++;
g=yes;
node *temp=new node;
temp->a=nostates;
temp->link=top1;
top1=temp;
news[nostates]=closure;
}
dttable[d][g][0]=inchar[j];
dttable[d][g][1]='\0';
cout<<"\n"< }
}
}
}
}
getch();
return;
}