c program to implement dfa

C program of dfa implementation. 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


Here is the c program to implement 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 :

c program to implement dfa

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

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 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.

If you like this post then consider sharing it with others.