DFA Driver

 Assignment 5 : DFA Driver

•   Finite automata is a mathematical model of a machine with finite number of internal configurations or states.
•  Input to the machine is from a finite set of symbols that forms the alphabet denoted by ∑. 
• Machine keeps on changing its state on consuming an input symbol and the state can be one among the finite set of states denoted by Q. 
• These transitions can be specified either by giving a transition table or a transition diagram denoted by δ.
• The machine always starts in a specific state which is designated as start state and is denoted as q0.
• There are some states in Q which are final states or accepting states. 
• The set of Final states is denoted by F. 
• Thus a Finite automata is characterized by these five components and mathematically it is a five tuple {Q, ∑, δ, qo, F}. 
• The language accepted by FA is the set of all strings for which the FA halts in a final state. 
• The languages accepted by FA are Regular languages. 
• In case of Deterministic FA , the transitions are uniquely defined on a state and input symbol.
•  DFA driver is a software that helps to construct a DFA and execute it on a string.

Data Structure  

DFA:-  DFA consists of number of states, number of symbol, transition table, start state is assumed by default as 0 and the Boolean array of final states 

struct DFA 

{ 

int m; // no of states

 int n; //no of symbols 

int delta[10][10]// transition table

 int final[10];// array of final states

 }

Slot I 

ii) Implement a DFA driver that allows initializing a DFA, display and executes a DFA

#include<stdio.h>

int nos=4;

int noi=2;

char input_symb[]={'a','b'};

int nof=1,final=2;

int d[][2]={{1,3},{1,2},{1,2},{3,3}};

char input_str[100];

int main()

{

int i,j,curr;

printf("M=(Q,E,d,q0,F)\n");

printf("Q={");

for(i=0;i<nos;i++)

printf("q%d,",i);

printf("\b}\nE={");

for(i=0;i<noi;i++)

printf("%c,",input_symb[i]);

printf("\b}\nq0=q0\nF={q%d}\nd:\n\t",final);

for(i=0;i<noi;i++)

printf("%c\t",input_symb[i]);

printf("\n");

for(i=0;i<nos;i++)

{

printf("q%d\t",i);

for(j=0;j<noi;j++)

printf("q%d\t",d[i][j]);

printf("\n");

}

do

{

printf("Enter input string:");

scanf("%s",input_str);

curr = 0;

for(i=0;input_str[i]!='\0';i++)

{

printf("d(q%d,%s)\n",curr,

input_str+i);

curr=d[curr][input_str[i]-input_symb[0]];

}

printf("q%d\n",curr);

if(curr==final)

printf("Accept\n");

else

printf("Reject\n");

printf("Continue Y(1)/N(0)?");

scanf("%d",&j);

}while(j==1);

return 0;

}

/************************OUTPUT****************

M=(Q,E,d,q0,F)

Q={q0,q1,q2,q3,}

E={a,b,}

q0=q0

F={q2}

d:

a b

q0 q1 q3

q1 q1 q2

q2 q1 q2

q3 q3 q3

Enter input string:aaabbaaa

d(q0,aaabbaaa)

d(q1,aabbaaa)

d(q1,abbaaa)

d(q1,bbaaa)

d(q2,baaa)

d(q2,aaa)

d(q1,aa)

d(q1,a)

q1

Reject

Continue Y(1)/N(0)?1

Enter input string:aabb

d(q0,aabb)

d(q1,abb)

d(q1,bb)

d(q2,b)

q2

Accept

Continue Y(1)/N(0)?0

/******************************************************************

iii) Extend DFA driver to accept DFA details from user

#include<stdio.h>

#include<stdlib.h>

#define MAX 10

int nos,noi,nof,finals[MAX],trans[MAX][MAX];

char input_symb[MAX],input_str[100];

void read_dfa()

{

int i,j;

printf("Enter no.of states:");

scanf("%d",&nos);

printf("Enter no.of input symbols:");

scanf("%d",&noi)

printf("Enter input symbols:");

scanf("%s",input_symb);

printf("Enter no.of finals:");

scanf("%d",&nof);

printf("Enter finals states:");

for(i=0;i<nof;i++)

scanf("%d",&finals[i]);

printf("Enter transition table:\n");

for(i=0;i<nos;i++)

{

for(j=0;j<noi;j++)

{

printf("d(q%d,%c)=",

i,input_symb[j]);

scanf("%d",&trans[i][j]);

}

}

}

void show_trans()

{

int i,j;

printf("M=(Q,E,d,q0,F)\n");

printf("Q={");

for(i=0;i<nos;i++)

printf("q%d,",i);

printf("\b}\nE={");

for(i=0;i<noi;i++)

printf("%c,",input_symb[i]);

printf("\b}\nq0=q0\nF={");

for(i=0;i<nof;i++)

printf("q%d,",finals[i]);

printf("\b}\nd:\n\t");

for(i=0;i<noi;i++)

printf("%c\t",input_symb[i]);

printf("\n");

for(i=0;i<nos;i++)

{

printf("q%d\t",i);

for(j=0;j<noi;j++)

printf("q%d\t",trans[i][j]);

printf("\n");

}

}

void check()

{

int i,j,curr;

printf("Enter input string:");

scanf("%s",input_str);

curr = 0;

for(i=0;input_str[i]!='\0';i++)

{

printf("d(q%d,%s)\n",curr,input_str+i);

curr = trans[curr][input_str[i]-input_symb[0]];

}

printf("q%d\n",curr);

for(i=0;i<nof;i++)

{

if(finals[i]==curr)

{

printf("Accept\n");

return;

}

}

printf("Reject\n");

}

int main()

{

int ch;

while(1)

{

printf("1.Read DFA\n2.Show Transition Table\n3.Check acceptance of given string\n4.Exit\n");

printf("Enter choice (1-4):");

scanf("%d",&ch);

switch(ch)

{

case 1:

read_dfa();

break;

case 2:

show_trans();

break;

case 3:

check();

break;

case 4:

exit(0);

}

}

return 0;

}