C code to eliminate productions in a Grammar

C program to eliminate the productions that do not produce terminal in a grammar.

#include<stdio.h> 

int check(char ,int ); 
int flag=0; 
char a[20][20]; 
int main() 
{ 
int i=0,j=0,k,n,p; 
char c; 
FILE *fp; 
//clrscr(); 
fp=fopen("input.txt","r"); 
while(fscanf(fp,"%c",&c)!=EOF) 
{ 
 if(c=='|') 
 { 
 a[i][j]='\n'; 
 j=0,i++; 
 a[i][j]=a[i-1][j++]; 
 a[i][j++]='-'; 
 a[i][j++]='>'; 
 } 
 else if(c!='\n') 
   a[i][j++]=c; 
 else 
 { 
 a[i][j]=c; 
 i++; 
 j=0; 
 }
} 
n=i; 
j=i=0; 
fclose(fp); 
printf("\n\tStart symbol is S\n\tCapital latters are variables\n\tSmall latters are terminals\n"); 
printf("\n:::::::::::----INPUT-----::::::::::::\n\n"); 
while(i<n) 
{ 
 if(a[i][j]!='\n') 
  printf("%c",a[i][j++]); 
 else 
 { 
  printf("%c",a[i][j]); 
  i++; 
  j=0; 
 }
} 
i=0; 
j=3; 
while(i<n) 
{ 
if(a[i][j]!='\n') 
{ 
 if(a[i][j]=='S') 
  j++; 
 if(a[i][j]>='a'&&a[i][j]<='z') 
  j++; 
 if(a[i][j]>='A'&&a[i][j]<='Z') 
 { 
    
 check(a[i][j],n); 
 if(flag==1) 
 { 
   a[i][0]=' '; 
 }  
 j++; 
  }   //ifA 
 }    //if'/n' 
 else 
 { 
 i++; 
 j=3; 
 } 
}  
//while// 
i=j=0; 
printf("\n:::::::::::----OUTPUT-----::::::::::::\n\n"); 
while(i<n) 
{ 
 if(a[i][j]==' ') 
 { 
 i++; 
 j=0; 
 } 
 else if(a[i][j]!='\n') 
 printf("%c",a[i][j++]); 
 else 
 { 
 printf("%c",a[i][j]); 
 i++; 
 j=0; 
 }
} 
//getch(); 
} 

  
int check(char c,int n) 
{ 
//char b; 
int i=0,p,j=3; 

for(i=0;i<n;i++) 
  if(a[i][0]==c) 
  {  
 flag=0; 
   break;   
  } 
  else 
   flag=1; 
while(a[i][j]!='\n'&&flag!=1) 
{ 
 if(a[i][j]=='S'||a[i][j]==c) 
  j++; 

 if(a[i][j]>='a'&&a[i][j]<='z') 
  j++; 

 if(a[i][j]>='A'&&a[i][j]<='Z') 
 { 
  check(a[i][j],n); 
   j++; 
  } 
 }
}

INPUT FILE (input.txt):-

S->ASa|ASB|ASC|AB
A->a
B->b
C->D

Output:-

Related Programs:-

★ Regular Grammar

★ SLR Parser

★ Context Free Grammar (CFG)

★ DFA (Deterministic Finite Automata)

★ NFA (Non-Deterministic Finite Automata)

C code to calculate In and Out in TAC

// C code to calculate in and out for each block in a given three address code(TAC). //

C program:

#include<stdio.h>
#include<string.h>
#include<math.h>

void rm_duplicate(int leader[100])
{
int i,j;
int array_size;
i=0;
while(leader[i++]!='\0')
{
          array_size=i;
}

j=0;

for(i=0;i<array_size;i++)
          {
                    if (leader[i] != leader[j])
                    {
                              j++;
                              leader[j] = leader[i]; // Move it to the front
                    }
          }

leader[j+1]='\0';
}


void find_gen(int leader[100],int gen_matrix[100][100],char tac[100][100],int block_count,int lines)
{        
          int i,j;
          char *if_equal;
          for(i=0;i<100;i++)
          {
                    for(j=0;j<100;j++)
                    {
                              gen_matrix[i][j]=0;
                    }
          }
          for(i=0;i<block_count-1;i++)
          {
                    for(j=leader[i]-1;j<leader[i+1]-1;j++)
                    {
                              if_equal=strstr(tac[j],"=");     
                              if(if_equal)
                              {
                                        gen_matrix[i][j]=1;
                              }               
                    }
          }

          for(j=leader[block_count-1]-1;j<lines;j++)
          {
                    if_equal=strstr(tac[j],"=");     
                    if(if_equal)
                    {
                              gen_matrix[block_count-1][j]=1;
                    }
          }

        
}

void find_kill(int leader[100],int kill_matrix[100][100],char tac[100][100],int block_count,int lines)
{
          int i,j,k;
          for(i=0;i<100;i++)
          {
                    for(j=0;j<100;j++)
                    {
                              kill_matrix[i][j]=0;
                    }
          }
          for(i=0;i<block_count-1;i++)
          {
                    for(j=leader[i]-1;j<leader[i+1]-1;j++)
                    {
                              for(k=0;k<lines;k++)
                              {
                                        if(k<leader[i]-1 || k>=leader[i+1]-1)
                                        {
                                                  if(tac[j][0]==tac[k][0] && tac[j][0]!='i' && tac[j][0]!='g')
                                                  {
                                                            kill_matrix[i][k]=1;
                                                  }
                                        }
                              }
                    }
          }
         
          for(j=leader[block_count-1]-1;j<lines;j++)
                    {
                              for(k=0;k<lines;k++)
                              {
                                        if(k<leader[block_count-1]-1 || k>leader[block_count-1])
                                        {
                                                  if(tac[j][0]==tac[k][0] && tac[j][0]!='i' && tac[j][0]!='g')
                                                  {
                                                            kill_matrix[block_count-1][k]=1;
                                                  }
                                        }
                              }
                    }
                   
}
         



int find_block(int col,int leader[100],int lines)
{
          int i=0,j;
          while(leader[i]!='\0')
          {
                    if(col>=leader[i] && col<leader[i+1])
                    {
                              return i+1;
                              break;
                    }
                    i++;
          }
          if(col>=leader[i-1] && col<=lines)
                    {
                              return i;
                    }
          else
                    return 0;
}
                             

find_predecessor(int flow_graph[100][100],int block_count,int predecessor[100][100])
{
int i,j;
for(i=0;i<block_count;i++)
{
          for(j=0;j<block_count;j++)
          {
                    predecessor[j][i]=flow_graph[i][j];
          }
}
for(i=0;i<block_count;i++)
{
          printf("\npredecessor of block %d :",i+1);
          for(j=0;j<block_count;j++)
                    {
                              if(predecessor[i][j]==1)
                              {
                                        printf("%d ",j+1);
                              }
                    }
}
printf("\n\n");
}

void copy(int a[100][100],int b[100][100])
{                             
          int x,y;
          for(x=0;x<100;x++)
          for(y=0;y<100;y++)
          b[x][y]=a[x][y];
}      

                  
void find_in(int gen_matrix[100][100],int kill_matrix[100][100],int flow_graph[100][100],int block_count,int lines,int in_matrix[100][100],int out_matrix[100][100])
{
          int i,j,k,l;
          int ctr=0;
          int predecessor[100][100];
          int cpy_in[100][100],cpy_out[100][100];
          find_predecessor(flow_graph,block_count,predecessor);
         
       
        
          while(1)
          {
                    copy(in_matrix,cpy_in);
                    copy(out_matrix,cpy_out);
                   
                    for(i=0;i<block_count;i++)
                    {
                              for(k=0;k<block_count;k++)
                              {
                                        if(predecessor[i][k] == 1)
                                        {
                                                  for(l=0;l<lines;l++)
                                                  in_matrix[i][l]= in_matrix[i][l] | out_matrix[k][l];
                                        }
                              }
                              for(l=0;l<lines;l++)
                              out_matrix[i][l]=out_matrix[i][l] | (gen_matrix[i][l] | ((in_matrix[i][l]==1 && kill_matrix[i][l]==0)?1:0));
                    }
                   
                    ctr++;
                   
                             
                               for(i=0;i<block_count;i++)//print
                              {
                                        printf("\n %d   :",i+1);
                                        for(j=0;j<lines;j++)
                                        {
                                                printf("%d ",in_matrix[i][j]);
                                        }
                              }
                             
                              printf("\n");
                             
                              for(i=0;i<block_count;i++)
                              {
                                        printf("\n %d   :",i+1);
                                        for(j=0;j<lines;j++)
                                        {
                                                printf("%d ",out_matrix[i][j]);
                                        }
                              }
                             
                    if(same_to_same(in_matrix,cpy_in) && same_to_same(out_matrix,cpy_out))
                    break;
          }
          printf("\nPasses required : %d",ctr);
}


                      
                        
int same_to_same(int a[100][100],int b[100][100])
{                             
          int x,y;
          for(x=0;x<100;x++)
          for(y=0;y<100;y++)
          {
                    if(b[x][y] != a[x][y])
                    return 0;
          }
          return 1;
}   

         
int main(void)
{
char tac[100][100],ch,*go_yes,*go_if,*if_equal;
int i=0,j=0,k,col,l,m,temp;
int lines,leader[100],block_count,block_no,last_line;
int gen_matrix[100][100],kill_matrix[100][100],in_matrix[100][100],out_matrix[100][100],flow_graph[100][100];
int predecessor[100][100];
FILE *fp;

fp=fopen("mytac.txt","r");
while((ch=fgetc(fp))!=EOF)
{
          if(ch=='\n')
          {
                    tac[i][j]='\0';
                    i++;
                    j=0;
          }
          else
          {
                    tac[i][j++]=ch;
          }
}
                   
lines=i;

printf("\n\nThe TAC is:\n\n");

for(i=0;i<lines;i++)
{         j=0;
          printf("%d  :",i+1);
          while(tac[i][j++]!='\0')
          {
                    printf("%c",tac[i][j-1]);
                   
          }
          printf("\n");
}

k=1;
leader[0]=1;
for(i=1;i<lines;i++)
{        
          go_yes=strstr(tac[i],"goto");
          if(go_yes)
          {        
                 
                    col=atoi(go_yes+5);
                    printf("%d line %d\n",i+1,col);
                    leader[k++]=col;             
                    if(i+2<=lines)
                    {
                              leader[k++]=i+2;
                    }
           }
}

leader[k]='\0';

i=0;
while(leader[i++]!='\0')
{
          for(j=i;j<k;j++)
          {        
                    if(leader[i-1]>leader[j])
                    {
                              temp=leader[i-1];
                              leader[i-1]=leader[j];
                              leader[j]=temp;
                    }
          }
}

rm_duplicate(leader);

printf("\n\nThe leaders are :");
i=0;
while(leader[i++]!='\0')
{
          printf("%d ",leader[i-1]);
}         

printf("\n\nblocks are:\n");

i=0;
while(leader[i+1]!='\0')
{
          printf("\nBlock %d :%d - %d",i+1,leader[i],leader[i+1]-1);
          i++;
}
printf("\nBlock %d :%d - %d\n\n",i+1,leader[i],lines);

block_count=i+1;

find_gen(leader,gen_matrix,tac,block_count,lines);

printf("\n\nGen\n");

for(i=0;i<block_count;i++)
{
          printf("\n %d   :",i+1);
          for(j=0;j<lines;j++)
          {
                  printf("%d ",gen_matrix[i][j]);
          }
}
printf("\n\n");

find_kill(leader,kill_matrix,tac,block_count,lines);

printf("\n\nKill\n");
for(i=0;i<block_count;i++)
          {
                    printf("\n %d   :",i+1);
                    for(j=0;j<lines;j++)
                    {
                              printf("%d ",kill_matrix[i][j]);
                    }
          }
printf("\n\n");



//k=0;
for(i=0;i<block_count-1;i++)
{
          last_line=leader[i+1]-2;
          go_yes=strstr(tac[last_line],"goto");
          col=last_line+1;
          block_no=find_block(col,leader,lines);               
          if(go_yes)
          {
                    col=atoi(go_yes+5);
                    go_if=strstr(tac[last_line],"if");
                   
                    if(go_if)
                    {
                              flow_graph[i][block_no]=1;
                              block_no=find_block(col,leader,lines);
                              flow_graph[i][block_no-1]=1;
                    }
                    else
                    {
                              block_no=find_block(col,leader,lines);
                              flow_graph[i][block_no-1]=1;
                    }
                   
          }
          else
          {
                    col=last_line+1;
                    block_no=find_block(col,leader,lines);
                    flow_graph[i][block_no]=1;
          }
}

last_line=lines-1;
go_yes=strstr(tac[last_line],"goto");
if(go_yes)
{
          col=atoi(go_yes+5);
          block_no=find_block(col,leader,lines);
          go_if=strstr(tac[last_line],"if");
          flow_graph[block_count-1][block_no-1]=1;
}

printf("\n\nFlow graph is:\n\n   ");
for(i=0;i<block_count;i++)
{
          printf("%d ",i+1);
}
for(i=0;i<block_count;i++)
{        
          printf("\n%d :",i+1);
          for(j=0;j<block_count;j++)
          {
                    printf("%d ",flow_graph[i][j]);
          }
}
printf("\n\n");
//find_predecessor(flow_graph,block_count,predecessor);

for(i=0;i<100;i++)
{
          for(j=0;j<100;j++)
          {
                    in_matrix[i][j]=0;
                    out_matrix[i][j]=0;
          }
}

find_in(gen_matrix,kill_matrix,flow_graph,block_count,lines,in_matrix,out_matrix);

printf("\n\nIn\n");

for(i=0;i<block_count;i++)
{
          printf("\n %d   :",i+1);
          for(j=0;j<lines;j++)
          {
                  printf("%d ",in_matrix[i][j]);
          }
}
printf("\n\n");


printf("\n\nOut\n");

for(i=0;i<block_count;i++)
{
          printf("\n %d   :",i+1);
          for(j=0;j<lines;j++)
          {
                  printf("%d ",out_matrix[i][j]);
          }
}
printf("\n\n");
}




Input File:

p=m-1
j=n
u=n
p=p+1
j=j-1
if p<j goto 9
a=u2
goto 4
p=u3
goto 4

For more C programs related to Automata, Check Automata label. Share and comment to improve this blog.

Related Programs:-

★ DFA (Deterministic Finite Automata)

★ NFA (Non-Deterministic Finite Automata)

★ Convert NFA to DFA

★ Lexical Analyzer

★ Syntax Tree

C code to Implement Syntax Tree

/* C program to Implement Syntax Tree. */


#include<conio.h>
#include<stdio.h>

void main()
{
FILE *fp;
int i=0,j=0,k,l,row,col,s,x;
char a[10][10],ch,main[50],search;
clrscr();
fp=fopen("syntax.txt","r+");

while((ch=fgetc(fp))!=EOF)
{
if(ch=='\n')
    {
    row=i;
    col=j;
    j=0;
    i++;
    }

else
    {
    a[i][j]=ch;
    j++;
    }
}

printf("\n");
for(k=0;k<row+1;k++)
{
for(l=0;l<col;l++)
{
printf("%c",a[k][l]);
}
printf("\n");
}
i=0;
s=0;
for(k=0;k<row+1;k++)
{
        main[i]=a[k][1];
        i++;
        if(a[k][3]=='t')
        {
            search=a[k][4];
            for(l=0;l<i;l++)
            {
            if(main[l]==search)
                {
                main[i]=main[l];
                i++;
                break;
                }
            }
        main[i]=a[k][5];
        s=5;
        i++;
        }
        else
        {
            main[i]=a[k][3];
               //    printf("\n%c",main[i]);
            i++;
            main[i]=a[k][4];
               //    printf(",%c\n",main[i]);
            s=4;
            i++;
        }

        s++;

        if(a[k][s]=='t')
        {
        s++;
        search=a[k][s];

        for(l=0;l<i;l++)
            {
            if(main[l]==search)
                {
                main[i]=main[l];
                i++;
                break;
                }
            }
        }

        else
        {
        main[i]=a[k][s];
        i++;
        }

}

        for(x=i-1;x>=0;x=x-4)
        {
        printf("\ntt%c: root->%c ",main[x-3],main[x-1]);
        if(main[x-2]>48 &&main[x-2]<59)
            printf("lc->t%c ",main[x-2]);
        else
            printf("lc->%c ",main[x-2]);

        if(main[x]>48 &&main[x]<59)
            printf("rc->t%c ",main[x]);
        else
            printf("rc->%c ",main[x]);
        }

getch();
}


Input File For Syntax Tree program:

t1=a+b
t2=c-d
t3=e+t2
t4=t1-t3

For more C programs related to Automata, Check Automata label. Share and comment to improve this blog.

Related Programs:-

★ Context Free Grammar (CFG)

★ DFA (Deterministic Finite Automata)

★ NFA (Non-Deterministic Finite Automata)

★ Convert NFA to DFA

★ Lexical Analyzer

C code to implement Lexical Analyzer

C program to implement Lexical Analyzer

#include<stdio.h> 
#include<string.h> 
#include<stdlib.h>

void removeduplicate(); 
void final();
int Isiden(char ch);
int Isop(char ch);
int Isdel(char ch);
int Iskey(char * str);
void removeduplicate();

char op[8]={'+','-','*','/','=','<','>','%'}; 
char del[8]={'}','{',';','(',')','[',']',','}; 
char *key[]={"int","void","main","char","float"}; 

//char *operato[]={"+","-","/","*","<",">","=","%","<=",">=","++"}; 

int idi=0,idj=0,k,opi=0,opj=0,deli=0,uqdi=0,uqidi=0,uqoperi=0,kdi=0,liti=0,ci=0; 
int uqdeli[20],uqopi[20],uqideni[20],l=0,j; 
char uqdel[20],uqiden[20][20],uqop[20][20],keyword[20][20]; 
char iden[20][20],oper[20][20],delem[20],litral[20][20],lit[20],constant[20][20]; 

void lexanalysis(char *str) 
 { 
   int i=0; 
   while(str[i]!='\0') 
    { 
     if(Isiden(str[i]))     //for identifiers 
       { 
          while(Isiden(str[i])) 
        { 
            iden[idi][idj++]=str[i++]; 
        } 
          iden[idi][idj]='\0'; 
          idi++;idj=0; 
       } 
      else 
      if(str[i]=='"')         //for literals 
         { 
         lit[l++]=str[i]; 
         for(j=i+1;str[j]!='"';j++) 
           { 
            lit[l++]=str[j]; 
           } 
         lit[l++]=str[j];lit[l]='\0'; 
         strcpy(litral[liti++],lit); 
         i=j+1; 
         } 
      else 
      if(Isop(str[i]))        // for operators 
          { 
         while(Isop(str[i])) 
            { 
             oper[opi][opj++]=str[i++]; 
            } 
         oper[opi][opj]='\0'; 
         opi++;opj=0; 
          } 
       else 
       if(Isdel(str[i]))     //for delemeters 
          { 
          while(Isdel(str[i])) 
            { 
              delem[deli++]=str[i++]; 
            } 
           } 
        else 
           { 
            i++; 
        } 
     } 

   removeduplicate(); 
   final(); 
} 

int Isiden(char ch) 
 { 
   if(isalpha(ch)||ch=='_'||isdigit(ch)||ch=='.') 
   return 1; 
   else 
   return 0; 
 } 

int Isop(char ch) 
 { 
  int f=0,i; 
  for(i=0;i<8&&!f;i++) 
   { 
    if(ch==op[i]) 
     f=1; 
   } 
 return f; 
} 

int Isdel(char ch) 
 { 
  int f=0,i; 
  for(i=0;i<8&&!f;i++) 
   { 
    if(ch==del[i]) 
     f=1; 
   } 
 return f; 
 } 

int Iskey(char * str) 
{ 
  int i,f=0; 
  for(i=0;i<5;i++) 
   { 
    if(!strcmp(key[i],str)) 
      f=1; 
    } 
  return f; 
} 

void removeduplicate() 
 { 
   int i,j; 
   for(i=0;i<20;i++) 
    { 
     uqdeli[i]=0; 
     uqopi[i]=0; 
     uqideni[i]=0; 
    } 
   for(i=1;i<deli+1;i++)  //removing duplicate delemeters 
     { 
       if(uqdeli[i-1]==0) 
     { 
           uqdel[uqdi++]=delem[i-1]; 
           for(j=i;j<deli;j++) 
          { 
               if(delem[i-1]==delem[j]) 
                uqdeli[j]=1; 
          } 
      } 
     } 

    for(i=1;i<idi+1;i++)  //removing duplicate  identifiers 
       { 
      if(uqideni[i-1]==0) 
         { 
        strcpy(uqiden[uqidi++],iden[i-1]); 
        for(j=i;j<idi;j++) 
         { 
            if(!strcmp(iden[i-1],iden[j])) 
               uqideni[j]=1; 
         } 
          } 
    } 

     for(i=1;i<opi+1;i++)  //removing duplicate  operators 
     { 
        if(uqopi[i-1]==0) 
           { 
           strcpy(uqop[uqoperi++],oper[i-1]); 
           for(j=i;j<opi;j++) 
             { 
               if(!strcmp(oper[i-1],oper[j])) 
                 uqopi[j]=1; 
             } 
           } 
     } 

 } 
void final() 
 { 
  int i=0; 
  idi=0; 
  for(i=0;i<uqidi;i++) 
   { 
     if(Iskey(uqiden[i]))        //identifying keywords 
     strcpy(keyword[kdi++],uqiden[i]); 
     else 
      if(isdigit(uqiden[i][0]))    //identifying constants 
     strcpy(constant[ci++],uqiden[i]); 
     else 
     strcpy(iden[idi++],uqiden[i]); 
   } 

// printing the outputs 

printf("\n\tDelemeter are : \n"); 
for(i=0;i<uqdi;i++) 
printf("\t%c\n",uqdel[i]); 

printf("\n\tOperators are : \n"); 
for(i=0;i<uqoperi;i++) 
 { 
 printf("\t"); 
 puts(uqop[i]); 
 } 

printf("\n\tIdentifiers are : \n"); 
for(i=0;i<idi;i++) 
 { 
  printf("\t"); 
  puts(iden[i]); 
 } 

printf("\n\tKeywords are : \n"); 
for(i=0;i<kdi;i++) 
 { 
  printf("\t"); 
  puts(keyword[i]); 
 } 

printf("\n\tConstants are :\n"); 
for(i=0;i<ci;i++) 
  { 
  printf("\t"); 
  puts(constant[i]); 
  } 

printf("\n\tLiterals are :\n"); 
for(i=0;i<liti;i++) 
 { 
   printf("\t"); 
   puts(litral[i]); 
 } 
} 
void main() 
{ 
  char str[50]; 
  //clrscr(); 
  printf("\nEnter the string : "); 
  scanf("%[^\n]c",str);
  lexanalysis(str); 
  //getch(); 
}

Output:-

Related Programs:-

★ Find out First and Follow in a given Grammar

★ Regular Grammar

★ SLR Parser

★ Context Free Grammar (CFG)

★ DFA (Deterministic Finite Automata)

C code to convert NFA into DFA

C program to convert NFA(Non-deterministic Finite Automata) to DFA(Deterministic Finite Automata). Add given below text file to your current directory to check this program. This program is tested on Turbo C.

#include<stdio.h>

int Fa[10][10][10],states[2][10],row=0,col=0,sr=0,sc=0,th=0,
in,stat,new_state[10][10],max_inp=-1,no_stat;
FILE *fp;

int search(int search_var)
 {

   int i;
   for(i=0;i<no_stat;i++)
      if(search_var == states[1][i])
      return 1;
   return 0;
 }


int sort(int *arr,int count)
 {
   int temp,i,j;
   for(i=0;i<count-1;i++)
     {
      for(j=i+1;j<count;j++)
    {
      if(arr[i]>=arr[j])
        {
          temp=arr[i];
          arr[i]=arr[j];
          arr[j]=temp;
         }
     }
     }
   return 0;
 }

int checkcon(int *arr,int *count)  //for doing this {4,1}={1,2,1}=={1,2}
 {
   int i,temp,j,k,c,t,m;
   for(i=0;i<*count;i++)
     {
       if(arr[i]>row)
      {
         temp =arr[i];
         c=0;
         t=0;
        while(new_state[arr[i]][t]!=-1)
         {
           t++;
           c++;
         }
        //right shift from ith postion (c-2) th time
        for(k=0;k<=c-2;k++)
           {
        for(j=9;j>=i+1+k;j--)
         {
          arr[j]=arr[j-1];
         }
           }

         t=0;
         for(j=i;j<c;j++)
        {
           arr[j]=new_state[temp][t];
           t++;
         }
       }
     }
   c=0;
  for(i=0;arr[i]!=-1;i++)
      c++;
   *count=c;
   return 0;
 }

int remove_duplicate(int *arr,int *count)
 {
   int i,j=0;
   for(i=1;i<*count;i++)
     {
      if(arr[i]!=arr[j])
     {
       j++;
       arr[j]=arr[i];
     }
     }
   *count=j+1;
   return 0;
 }

int check(int i ,int j,int c,int *name)///for checking is this a new state?
  {
    int t,l,f;
    for(l=0;l<=stat;l++)
      {
       t=0; f=0;
       while(Fa[i][j][t]!=-1)
     {
        if(Fa[i][j][t]==new_state[l][t])
          t++;
        else
          {
        f=1;
        break;
         }
     }
      if((t==c)&&!f)
    {
     *name=l;
     return 1;
    }
    }
    return 0;
}

int trans(int i ,int j,int t,int c,int *count,int *arr)//transition o/p for particular i/p on states
 {
   int k=0,co,temp;
   *count=0;
   for(k=0;k<c;k++)
     {
       temp=Fa[i][j][k];
       co=0;
       while(Fa[temp][t][co]!=-1)
      {
        arr[*count]=Fa[temp][t][co++];
        (*count)++;
      }
     }
return 0;
 }

int nfa2dfa(int start,int end)
 {
   int j,t,c,i,k,count,arr[10],name,l;
   for(i=start;i<=end;i++)
      {
    for(j=0;j<=max_inp;j++)
      {
        c=0;t=0;
        while(Fa[i][j][t]>=0)
           {
         t++;
         c++;
           }
          if(c>1)
        {
         if(check(i,j,c,&name)==0)
           {
             for(k=0;k<c;k++)
              {
             new_state[stat][k]=Fa[i][j][k];
             for(l=0;states[1][l]!=-1;l++)
                if(new_state[stat][k] == states[1][l]&& !search(stat))
                  states[1][no_stat++]=stat;
              }

              for(t=0;t<=max_inp;t++)
            {
               count=0;
               for(k=0;k<10;k++)
                  arr[k]=-1;
               trans(i,j,t,c,&count,arr);


               checkcon(arr,&count);

               sort(arr,count);
               remove_duplicate(arr,&count);

               for(k=0;k<count;k++)
                 Fa[stat][t][k]=arr[k];
            }
          Fa[i][j][0]=stat++;
          for(t=1;t<c;t++)
            Fa[i][j][t]=-1;
         }
           else
         {
           Fa[i][j][0]=name ;
           for(t=1;t<c;t++)
             Fa[i][j][t]=-1;
         }
          }
       }

     }
  return 0;
 }

int main()
 {

     int i,j,k,flag=0,start,end;
     char c,ch;
     fp=fopen("Nfa_ip.txt","r+");


     for(i=0;i<2;i++)
       for(j=0;j<10;j++)
     states[i][j]=-1;

    for(i=0;i<10;i++)
       for(j=0;j<10;j++)
     new_state[i][j]=-1;

     for(i=0;i<10;i++)
       for(j=0;j<10;j++)
      for(k=0;k<10;k++)
          Fa[i][j][k]=-1;

     while(fscanf(fp,"%d",&in)!=EOF)
       {
       fscanf(fp,"%c",&c);

        if(flag)
          {
         states[sr][sc++]=in;
         if(c=='\n')
            {
              sr++;
              sc=0;
            }
          }
        else if(c=='#')
          {
         flag=1;
         Fa[row][col][th]=in;

          }
         else if(!flag)
          {
         Fa[row][col][th]=in;
         if(c==',')
           {
             th++;
           }
         else if(c=='\n')
           {
             if(max_inp<col)
               max_inp=col;
              col=0;
              row++;
              th=0;
          }
        else if(c!=',')
         {
             col++;
             th=0;
          }
          }

      }
   no_stat=0;
   i=0;
   while(states[1][i++]!=-1)
      no_stat++;
      stat=row+1;
      start=0;end=row;
      while(1)
      {
         nfa2dfa(start,end);
         start=end+1;
         end=row;
         if(start>end)
          break;
      }

     printf("\n\nDFA IS : \n\n\n");
     for(i=0;i<=max_inp;i++)
     printf("\t%d",i);
     printf("\n");
     printf("----------------------------\n");

     for(i=0;i<stat;i++)
       {
     printf("%d-> |",i);
       for(j=0;j<=max_inp;j++)
      {
        printf("%2d        ",Fa[i][j][0]);
      }
      printf("\n");
       }
printf("\n\n");
printf("Total Number Of State Is : %d \n\n",stat);
printf("Final States Are : ");
  for(i=0;states[1][i]!=-1;i++)
     printf("%d ",states[1][i]);

printf("\n\n");
getch();
    return 0;
}

Input File For NFA to DFA:-

1,2 1
-1 2
-1 -1#
0
2

For more C programs related to Automata, Check Automata label. Share and comment to improve this blog.

Related Programs:-

★ Lexical Analyzer

★ Syntax Tree

★ Calculate In and Out

★ Eliminate productions in a Grammar that do not produce Terminal

★ Find out First and Follow in a given Grammar