PROGRAM 9 :

Write program to minimize any given DFA

ALGORITHM:

1.Get the start state, final state, input symbols as input and also give the edge value for each state.
2.Maintain a stack required for transition from one state to other state.
3.Using Pop or push function perform the insertion and deletion of elements when required.
4.Finally conversion has been made to change from given DFA to minimized DFA and the output is displayed as DFA transition table.

PROGRAM:

#include<stdio.h>
#include<string.h>
#define STATES 50
struct Dstate
{
char name;
char StateString[STATES+1];
char trans[10];    
int is_final;
}Dstates[50];
struct tran
{
char sym;
int tostates[50];
int notran;
};
struct state
{
int no;
struct tran tranlist[50];
};
int stackA[100],stackB[100],c[100],Cptr=-1,Aptr=-1,Bptr=-1;
struct state States[10];
char temp[STATES+1],inp[10];
int nos,noi,nof,j,k,nods=-1;

void pushA(int z)
{
stackA[++Aptr]=z;
}
void pushB(int z)
{
stackB[++Bptr]=z;
}

int popA()
{
return stackA[Aptr--];
}
void copy(int i)
{
char temp[STATES+1]=" ";
int k=0;
Bptr=-1;
strcpy(temp,Dstates[i].StateString);
while(temp[k]!='\0')
{
pushB(temp[k]-'0');
k++;
}
}
int popB()
{
return stackB[Bptr--];
}
int peekA()
{
return stackA[Aptr];
}
int peekB()
{
return stackA[Bptr];
}
int seek(int arr[],int ptr,int s)
{
int i;
for(i=0;i<=ptr;i++)
{

if(s==arr[i])
return 1;
}
return 0;
}
void sort()
{
int i,j,temp;
for(i=0;i<Bptr;i++)
{
for(j=0;j<(Bptr-i);j++)
{
if(stackB[j]>stackB[j+1])
{
temp=stackB[j];  
stackB[j]=stackB[j+1];
stackB[j+1]=temp;
}
}
  }
    }
void tostring()
{
int i=0;
sort();        
for(i=0;i<=Bptr;i++)
{      
temp[i]=stackB[i]+'0';
}
temp[i]='\0';
}
void display_DTran()
{
int i,j;
printf("\n\t\t DFA transition table");
printf("\n\t\t ---------------------------------------------- ");
printf("\n States \tString \tInputs\n");
for(i=0;i<noi;i++)
{
printf("\t %c",inp[i]);
}
printf("\n\t ------------------------------------------------- ");
for(i=0;i<nods;i++)
{
if(Dstates[i].is_final==0)
printf("\n%c",Dstates[i].name);
else
printf("\n*%c",Dstates[i].name);
printf("\t%s",Dstates[i].StateString);
for(j=0;j<noi;j++)
{
printf("\t%c",Dstates[i].trans[j]);
}
    }
     printf("\n");
}
void move(int st,int j)
{
int ctr=0;
while(ctr<States[st].tranlist[j].notran)
{
pushA(States[st].tranlist[j].tostates[ctr++]);
}
}
void lambda_closure(int st)
{
int ctr=0,in_state=st,curst=st,chk;
while(Aptr!=-1)
{
curst=popA();
ctr=0;
in_state=curst;
while(ctr<=States[curst].tranlist[noi].notran)
{
chk=seek(stackB,Bptr,in_state);
if(chk==0)
pushB(in_state);
in_state=States[curst].tranlist[noi].tostates[ctr++];
chk=seek(stackA,Aptr,in_state);
if(chk==0 && ctr<=States[curst].tranlist[noi].notran)
pushA(in_state);
}
     }
}
Void main()
{
int i,final[20],start,fin=0;
char c,ans,st[20];
printf("\n Enter no of states in NFA:");
scanf("%d",&nos);
for(i=0;i<nos;i++)
{
States[i].no=i;
}
printf("\n Enter the start states:");
scanf("%d",&start);
printf("Enter the no of final states:");
scanf("%d",&nof);
printf("Enter the final states:\n");
for(i=0;i<nof;i++)
scanf("%d",&final[i]);
printf("\n Enter the no of input symbols:");
scanf("%d",&noi);
c=getchar();
printf("Enter the input symbols:\n");
for(i=0;i<noi;i++)
{
scanf("%c",&inp[i]);
c=getchar();
}
g1inp[i]='e';
printf("\n Enter the transitions:(-1 to stop)\n");
for(i=0;i<nos;i++)
{
for(j=0;j<=noi;j++)
{
States[i].tranlist[j].sym=inp[j];
k=0;
ans='y';
while(ans=='y')
{
printf("move(%d,%c);",i,inp[j]);
scanf("%d",&States[i].tranlist[j].tostates[k++]);
if((States[i].tranlist[j].tostates[k-1]==-1))
{
k--;
ans='n';
break;
                      }
               }
States[i].tranlist[j].notran=k;
               }
}
i=0;nods=0,fin=0;
pushA(start);
lambda_closure(peekA());
tostring();
Dstates[nods].name='A';
nods++;
strcpy(Dstates[0].StateString,temp);
while(i<nods)
{
for(j=0;j<noi;j++)
{
fin=0;
copy(i);
while(Bptr!=-1)
{
move(popB(),j);
}

while(Aptr!=-1)
lambda_closure(peekA());
tostring();
for(k=0;k<nods;k++)
{
if((strcmp(temp,Dstates[k].StateString)==0))
{
Dstates[i].trans[j]=Dstates[k].name;
break;
}
}
if(k==nods)
{
nods++;
for(k=0;k<nof;k++)
{
fin=seek(stackB,Bptr,final[k]);
if(fin==1)
{
Dstates[nods-1].is_final=1;
break;
}
    }
strcpy(Dstates[nods-1].StateString,temp);
Dstates[nods-1].name='A'+nods-1;
Dstates[i].trans[j]=Dstates[nods-1].name; 
}
}
i++;
}
display_DTran();
}


OUTPUT:

Enter the no of input symbols:2
Enter the input symbols:
a ,b
Enter the transitions:(-1 to stop)
move(0,a);-1
move(0,b);-1
move(0,e);1
move(         0,e);7
move(0,e);-1
move(1,a);-1
move(1,b);-1
move(         1,e);2
move(1,e);4
move(1,e);-1
move(2,a);3
move(2,a);3
move(2,a);-1
move(2,b);-1
move(2,e);-1
move(3,a);-1
move(3,b);-1
move(3,e);6
move(3,e);-1
move(4,a);-1
move(4,b);-1
move(4,e);-1
move(5,a);-1
move(5,b);-1
move(5,e);6
move(5,e);1
move(5,e);-1
move(6,a);-1
move(6,b);-1
move(6,e);-1
move(7,a);-1
move(7,b);-1
move(7,e);-1

DFA transition table
States         String             Inputs
                                                                    a       b  
                           -------------------------------------------------
A                 01247              B       C
B                    36                 C       C
C                                         C      C