Theory Of Computation:Algorithm and Coding for Conversion of e -NFA to DFA.

Subset Construction:
 -closure (A,B,C,D,E)={A,B,C,D,E}
 d {(A,B,C,D,E),0}={A,C,E}
so,  -closure (A,C,E)={A,B,C,D,E}
d {(A,B,C,D,E),1}={E,B,D}
so,  -closure (B,E,D)={B,E,D}

 -closure (A)={A,B,D}
d {(A,B,D),0}={A,C,E}
so,  -closure (A,C,E)={A,B,C,D,E}
d {(A,B,D),1}={D,E}
So,  -closure (D,E)={D,E}

 -closure (D,E)={D,E}
d {(D,E),0}={E}
so,  -closure (E)=E
d {(D,E),1}={D}
So,  -closure (D)=D



d 0 1
                      {A,B,D} {A,B,D,C,E} {D,E}
*{A,B,C,D,E} {A,B,C,D,E} {B,E,D}
*{D,E} {E} {D}
*{B,E,D} {C,E} {D,E}
*{E} Ø Ø
{D} {E} {D}
*{C,E} Ø {B}
{B} {C} {E}
{C} Ø {B}
ؠؠØ

Algorithm:
Step 1: Get the string.
      for(k=0;k(x[k]=getchar())!='\n'; k++)
Step 2: Set count=k and flag=a (starting state).
Step 3: For k=0 to k<count
i. Check the flag.
ii. If flag=state(any possible state of automata), choose that state.
iii. Inside that state
If x[k]=1
flag=state1(i.e another state that is reached when input bit to present  state is 1).
   Else
flag=state2 (i.e another state that is  reached when input bit to present state is 0).
iv. Increment the value of k.
Step 4: If flag=any final state
         Display string is accepted.
             Else
                       Display string is not accepted.
Step 5: End of the program.

Coding:
#include<stdio.h>
#include<conio.h>
void main()
{
 int k,count,abd,abcde=2,de=3,bde=4,e=5,d=6,ce=7,b=8,c=9,phai=10,flag;
 char x[15];
 clrscr();
 printf("\n Evaluation for Equivalent DFA");
 printf("\n Enter the string:");
 for(k=0;(x[k]=getchar())!='\n';k++);
 count=k;
 flag=abd;
 for(k=0;k<count;k++)
 {
  if(flag==abd)
  {
   if(x[k]=='0')
    flag=abcde;
   else
    flag=de;
  }
  else if(flag==abcde)
  {
   if(x[k]=='0')
    flag=abcde;
   else
    flag=bde;
  }
  else if(flag==de)
  {
   if(x[k]=='0')
    flag=e;
   else
    flag=d;
  }
  else if(flag==bde)
  {
   if(x[k]=='0')
    flag=ce;
   else
    flag=de;
  }
  else if(flag==e)
  {
    flag=phai;
  }
  else if(flag==d)
  {
   if(x[k]=='0')
    flag=e;
   else
    flag=d;
  }
  else if(flag==ce)
  {
   if(x[k]=='0')
    flag=phai;
   else
    flag=b;
  }
  else if(flag==b)
  {
   if(x[k]=='0')
    flag=c;
   else
    flag=e;
  }
  else if(flag==c)
  {
   if(x[k]=='0')
    flag=phai;
   else
    flag=b;
  }
  else
  {
   flag=phai;
  }
 }
 if(flag==abcde||flag==bde||flag==ce||flag==de||flag==e)
   printf("\n String is accepted.");
 else
   printf("\n String is not accepted.");
 getch();
}