Scribd
Upload
7K views8 pages

Minimizing DFA C Program

This C program defines functions to process a deterministic finite automaton (DFA). It takes a grammar definition as input, groups non-terminal symbols that have identical transitions, and removes one of the grouped symbols from the DFA table. It gets the DFA inputs, defines groups of symbols, removes symbols from the DFA table based on the groups, and outputs the resulting DFA table.

Uploaded by

rnspace
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
7K views8 pages

Minimizing DFA C Program

This C program defines functions to process a deterministic finite automaton (DFA). It takes a grammar definition as input, groups non-terminal symbols that have identical transitions, and removes one of the grouped symbols from the DFA table. It gets the DFA inputs, defines groups of symbols, removes symbols from the DFA table based on the groups, and outputs the resulting DFA table.

Uploaded by

rnspace
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

#include <stdio.

h>
#include <conio.h>
#include <string.h>
void getInputs();
void defineGroups(int);
int isGroupDefined(char);
int isInitialState(char);
int isFinalState(char);
void removeFromDFA(char,char);
int posofstate(char);
void DFAOutput();
char
G[]="({A,B,C,D,E,F,G,H},{a,b},{A},{E})",DFA_initial[50],DFA_final
[50];
char *DFA_NT[50],
*DFA_T[50],
*DFA_Tab[50][50];
char groups[50][50],
groupedStates[50];
int DFA_NTlen,DFA_Tlen,totalGrouped,totalGroup,GSlen;
int main(void)
{
int i;
totalGrouped=0;
totalGroup=0;
GSlen=0;
getInputs();
for(i=0;i<DFA_NTlen;i++)
{
if(!isGroupDefined(DFA_NT[i][0]))

{
defineGroups(i);
}
}
for(i=0;i<GSlen;i+=2)
{
removeFromDFA(groupedStates[i],groupedStates[i+1]);
}

DFAOutput();
getch();
}
void getInputs()
{
int i=0,j=0,ct=0;
char c,str[100][100];
DFA_NTlen=0;
DFA_Tlen=0;
//printf("Enter Grammar Definition");
//gets(G);
j=2;
i=0;
c=' ';
while(c!='}') //N-Terminal
{
c=G[j];
if( c!=',' && c!='}')
{

str[ct][0]=G[j];
str[ct][1]='\0';
DFA_NT[i++]=str[ct++];
DFA_NTlen++;
}
j++;
}
j=j+2;
i=0;
c=' ';
while(c!='}') //Terminal
{
c=G[j];
if( c!=',' && c!='}')
{
str[ct][0]=G[j];
str[ct][1]='\0';
DFA_T[i++]=str[ct++];
DFA_Tlen++;
}
j++;
}
j=j+2;
i=0;
c=' ';
while(c!='}') //initial state
{
c=G[j];
if( c!=',' && c!='}')
{
c=G[j];

DFA_initial[i++]=c;
}
j++;
}
DFA_initial[i]='\0';
j=j+2;
i=0;
c=' ';
while(c!='}') //initial state
{
c=G[j];
if( c!=',' && c!='}')
{
c=G[j];
DFA_final[i++]=c;
}
j++;
}
DFA_final[i]='\0';
i=0;
printf("Input DFA Table:");
printf("\n\n\t %s",DFA_T[i++]);
while(i<DFA_Tlen)
{
printf("\t\t%s",DFA_T[i++]);
}
printf("\n\t%c",214);
for(i=0;i<DFA_NTlen;i++)
{
printf("\n %s\t%c ",DFA_NT[i],186);
for(j=0;j<DFA_Tlen;j++)
{
str[ct][0]=getche();

str[ct][1]='\0';
DFA_Tab[i][j]=str[ct++];
printf("\t\t");
}
}
}

void defineGroups(int i)
{
int j,m,n=i+1,k=0,t=0;
for(m=i;m<m+1;m++)
{
while(n < DFA_NTlen)
{
if(DFA_Tab[m][t][0] == DFA_Tab[n][t][0])
{
t=1;
if(DFA_Tab[m][t][0] == DFA_Tab[n][t][0])
{
groupedStates[totalGrouped++]=DFA_NT[m][0];
groupedStates[totalGrouped]='\0';
groupedStates[totalGrouped++]=DFA_NT[n][0];
groupedStates[totalGrouped]='\0';
totalGroup++;
GSlen+=2;
}
}
n++;
}
}
printf("\nGSLEN %d", GSlen);

printf("\nGrouped %s", groupedStates);


}
int isGroupDefined(char c)
{
if(strchr(groupedStates,c)==NULL)
return 0;
return 1;
}
int isInitialState(char c)
{
if(c == DFA_initial[0])
{
return 1;
}
return 0;
}
int isFinalState(char c)
{
if(c == DFA_final[0])
{
return 1;
}
return 0;
}
void DFAOutput()
{
int i,j;
printf("\n\nOutput\n");
for(i=0;i<DFA_Tlen;i++)

{
printf("\t%c",DFA_T[i][0]);
}
for(i=0;i<DFA_NTlen;i++)
{
printf("\n%c\t",DFA_NT[i][0]);
for(j=0;j<DFA_Tlen;j++)
{
printf("%c\t",DFA_Tab[i][j][0]);
}
}
}
void removeFromDFA(char c,char cc)
{
int xpos,ypos,i,j;
xpos=posofstate(c);
ypos=posofstate(cc);
if(xpos<ypos && !isFinalState(c) && !isFinalState(cc))
{
DFA_NT[ypos][0]='-';
DFA_Tab[ypos][0][0]='-';
DFA_Tab[ypos][1][0]='-';
for(i=0;i<DFA_NTlen;i++)
{
for(j=0;j<DFA_Tlen;j++)
{
if(DFA_Tab[i][j][0]==cc)
{
DFA_Tab[i][j][0]=c;
}
}
}

}
int posofstate(char state)
{
int i;
for(i=0;i<DFA_NTlen;i++)
{
if(DFA_NT[i][0]==state)
{
return i;
}
}
}

You might also like