OBJECTIVE: write a program for construction of minimized DFA from a given regular expression using C.
ALGORITHM:
- Get the start state, final state, input symbols as input and also give the edge value for each state.
- Maintain a stack required for transition from one state to other state.
- Using Pop or push function perform the insertion and deletion of elements when required.
- Finally conversion has been made to change from regular expression to minimized DFA and the output is displayed as DFA transition table.
#include
#include
#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
{
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
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