Implementation of NFA in C++

WAP to implement NFA over E={0,1} accepting the set of all strings that when interpreted in reverse as binary integer, is divisible by 5. Eg. L={0,10011, 1001100,…}

Algorithm:

• 1.       Start of the program
• 2.       Initialize variable for input and states
•    in[100] and state;
• 3.       Create a function tranFun() which takes a bit of input and current state as parameters and returns the transited state.
• 4.       Run a loop which passes  bits of input and current state to the function tranFun()            
• Store the intermediate transition state into variable temp and replace the value of state by latest transition state
• 5.       If the state is in accepting state then accept the string else reject the string.
• 6.       End of program.

Transition table:

State/input	0	1
q0*	q2	q0*
q1	q3	q0*
q2	q1	q3
q3	q4	q1
q4	q2	q4

Source code:

#include<iostream.h>

#include<conio.h>

int tranFun(char in, int state){

if(in=='0' && state==0){ return 0;}

else if(in=='1' && state==0){ return 2;}

else if(in=='0' && state==1){ return 3;}

else if(in=='1' && state==1){ return 0;}

else if(in=='0' && state==2){ return 1;}

else if(in=='1' && state==2){ return 3;}

else if(in=='0' && state==3){ return 4;}

else if(in=='1' && state==3){ return 1;}

else if(in=='0' && state==4){ return 2;}

else if(in=='1' && state==4){ return 4;}

}

void main()

{

                char in[100], temp[100];

   cout<<"enter input";

   cin>>in;

   int state=0;

   for(int i=0;i<strlen(in);i++){

                state=tranFun(in[i],state);

      cout<<"->q"<<state;

   }

   int len=strlen(in);

   if(state==0)

                cout<<"accepted";

   else

                cout<<"rejected";

   getch();

}

Output: