Search Tutorials

Friday 24 May 2013

C code to implement DFA(Deterministic Finite Automata)

/* C program to implement DFA(Deterministic Finite Automata). */

#include<stdio.h>
#include<conio.h>
int main()
{
  FILE * fp;
  int Fa[10][10],states[2][10],row=0,col=0,sr=0,sc=0,flag=0,i,j,in,curr;
  char k,*str;
  clrscr();
  fp = fopen("Dfa_ip.txt","r");
  if(fp==NULL)
  printf("file could not find\n");

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

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

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

    printf("THE AUTOMATA IS : \n\n");
    for (i=0;i<=row;i++)
       {
       for (j=0;j<col;j++)
         {
        printf("%2d ",Fa[i][j]);
         }
         printf("\n");
       }

     printf("\n\nEnter the string : ");
     gets(str);
     curr=states[0][0];
     i=0;
     while(str[i]!='\0')
       {
      curr=Fa[curr][str[i]-97];
      if(curr==-1)
         break;
      i++;
       }

      flag=0;
      if(curr!=-1)
       {
     for(i=0;i<=sc&&!flag;i++)
        {
           if(curr==states[1][i])
         {
            printf("\n\nSTRING ACCEPTED\n");
            flag=1;
            break;
         }
        }
       }
       if(flag==0)
      printf("\n\nSTRING NOT ACCEPTED ");
  getch();
  return 0;

}


Input File For DFA Program:

1 3
2 3
2 4
1 5
2 5
5 5#
0
1 4

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

Related Programs:-

★ NFA (Non-Deterministic Finite Automata)

★ Convert NFA to DFA

★ Lexical Analyzer

★ Syntax Tree

★ Calculate In and Out

8 comments:

  1. Hey your program doesnt works. Also pls tell me the format of input string.

    ReplyDelete
    Replies
    1. Already given in post..save input data in Dfa_ip.txt

      Delete
  2. What should we have in file Dfa_ip.txt? I mean that contents of languages of DFA or not. Please help me. Thanks

    ReplyDelete
    Replies
    1. 1 3
      2 3
      2 4
      1 5
      2 5
      5 5#
      0
      1 4

      Delete
    2. I don't understand. It's contents of Languages of DFA or not.

      Delete
    3. This comment has been removed by the author.

      Delete
  3. It is not going in for loop to accept the string

    ReplyDelete

Back to Top