My Project - Video Waker Alarm
Get Video alarm on Google Play

c program for dfa (deterministic finite automata)


c program for dfa (deterministic finite automata). Let us first know what is DFA or let us again revise the concept of DFA? Automation are basically language acceptor or language recognizer. A finite automata is a collection of 5-tuple(Q,∑,∂,q0,F). Where
Q=finite set of states
∑=input symbol
∂=transition function
q0=initial state
F=set of final state

c program for dfa

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

int ninputs;

int check(char,int ); //function declaration
int dfa[10][10];
char c[10], string[10];

int main()
{
     int nstates, nfinals;
     int f[10];
     int i,j,s=0,final=0;
     printf("enter the number of states that your dfa consist of \n");
     scanf("%d",&nstates);
     printf("enter the number of input symbol that dfa have \n");
     scanf("%d",&ninputs);
     printf("\nenter input symbols\t");

     for(i=0; i<ninputs; i++) 
     {
           printf("\n\n %d input\t", i+1);
           printf("%c",c[i]=getch());
     }

     printf("\n\nenter number of final states\t");
     scanf("%d",&nfinals);

     for(i=0;i<nfinals;i++)
     {
          printf("\n\nFinal state %d : q",i+1);
          scanf("%d",&f[i]);
     }

     printf("-----------------------------------------------------------------------");
     printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");

     for(i=0; i<ninputs; i++)
     {
          for(j=0; j<nstates; j++)
          {
               printf("\n(q%d , %c ) = q",j,c[i]);
               scanf("%d",&dfa[i][j]);
          }
     }

     do
     {
          i=0;
          printf("\n\nEnter Input String.. ");
          scanf("%s",string);

          while(string[i]!='\0')
          if((s=check(string[i++],s))<0)
          break;
          for(i=0 ;i<nfinals ;i++)
          if(f[i] ==s )
          final=1;
          if(final==1)
          printf("\n valid string"); 
          else
          printf("invalid string");
          getch();

          printf("\nDo you want to continue.?  \n(y/n) ");
     }
     while(getch()=='y');

     getch();
}
int check(char b,int d)
{
     int j;
     for(j=0; j<ninputs; j++)
     if(b==c[j])
     return(dfa[d][j]);
     return -1;
}

output of c program for dfa:

c program for dfa
c program for dfa

The above output is for the dfa to check whether the given binary number is even.
Its DFA is made as follows :

 c program for dfa
DFA: To check whether the given number is even

and its table is made as :

States-Input
0
1
q0
q2
q1
q1
q2
q1
q2
q2
q1

Uses of c program for dfa:  The very good example of finite state system is a control mechanism of elevator. It is very good tool for the programs such as text editors and lexical analyzer.
Thanks.

 


14 thoughts on “c program for dfa (deterministic finite automata)”

  1. it doesnt work, has a lot of errors, not on the code but on the logic of the program, i tried it already whit a lot of dfas and it doesnt work

  2. it doesnt work, has a lot of errors…
    “int final=0” is out of the do-while() so work only for first good string…
    it’s work only in that case, but try ∑={a,b} L[(a+b)*(a+b)a(a+b)*b]
    St | a | b
    q0 | q1 | q1
    q1 | q2 | q1
    q2 | q2 | q3
    q3 | q2 | q3

    and example “aab” or “bab” with your code is invalid… so something is wrong…

    1. This works correct! 🙂

      #include
      #include

      int ninputs;

      int check(char,int ); //function declaration
      int dfa[10][10];
      char c[10], string[10];

      int main()
      {
      int nstates, nfinals;
      int f[10];
      int i,j,s,final;
      printf(“enter the number of states that your dfa consist of \n”);
      scanf(“%d”,&nstates);
      printf(“enter the number of input symbol that dfa have \n”);
      scanf(“%d”,&ninputs);
      printf(“\nenter input symbols\t”);

      for(i=0; i<ninputs; i++)
      {
      printf("\n\n %d input\t", i+1);
      printf("%c",c[i]=getch());
      }

      printf("\n\nenter number of final states\t");
      scanf("%d",&nfinals);

      for(i=0; i<nfinals; i++)
      {
      printf("\n\nFinal state %d : q",i+1);
      scanf("%d",&f[i]);
      }

      printf("———————————————————————–");
      printf("\n\ndefine transition rule as (initial state, input symbol ) = final state\n");

      for(i=0; i<ninputs; i++)
      {
      for(j=0; j<nstates; j++)
      {
      printf("\n(q%d , %c ) = q",j,c[i]);
      scanf("%d",&dfa[i][j]);
      }
      }

      do
      {
      i=0, final=0, s=0;
      printf("\n\nEnter Input String.. ");
      scanf("%s",string);

      while(string[i]!='')
      if((s=check(string[i++],s))<0)
      break;
      for(i=0 ; i<nfinals ; i++)
      if(f[i] ==s )
      final=1;
      if(final==1)
      printf("\n valid string");
      else
      printf("invalid string");

      printf("\nDo you want to end? \n(t) ");
      }
      while(getch()!='t');

      getch();
      }
      int check(char b,int d)
      {
      int j;
      for(j=0; j<ninputs; j++)
      if(b==c[j]){
      printf("dfa[%d][%d] = %d\n", d,j,dfa[d][j]);
      return(dfa[j][d]);}
      return -1;
      }

  3. please would you write me a c+ program which accept all strings over {a,b} containing aab
    2) write for me a c program for doing binary subtraction and other c program for doing binary addition

Leave a Reply

Your email address will not be published. Required fields are marked *