C program to implement DFA

//updated on 11/03/2015

Hello friends,

               This post describes how a Deterministic Finte Automata (DFA) can be implemented using C. Do you know, associated with every programming language compiler there is a program named  recognizer that takes a string , say string S, as input and answers "YES" if S is a sentence of the language and  " NO " otherwise..!! To accomplish this , we have to train recognizer about the syntactic structure of intended language ( done with regular expressions). For this purpose, we construct a transition diagram called a "finite automation". In a Deterministic Finite Automation, only one transition out of state is possible on the same input symbol. On the other hand, in NonDeterministic Finite Automata more than one transitions may possible for same input symbol.

  . Some interesting implementations using DFA are:

• whether DFA accepts all strings.
• whether DFA accepts any string
• whether two DFAs recognize the same language
• DFA with a minimum number of states for a particular regular language

Illustartion


Consider the DFA represented in this transition diagram.



   

                         


Here is a sample DFA with starting state " 0 ", and accepting state " 1" .  "a" and "b" are the input symbols.
This DFA will accept any string containing 'a's and 'b' and last symbol should be 'a'.


CODE:


#include <stdio.h>

#define TOTAL_STATES 2

#define FINAL_STATES 1

#define ALPHABET_CHARCTERS 2

#define UNKNOWN_SYMBOL_ERR 0

#define NOT_REACHED_FINAL_STATE 1

#define REACHED_FINAL_STATE 2

enum DFA_STATES{q0,q1};

enum input{a,b};

int Accepted_states[FINAL_STATES]={q1};

char alphabet[ALPHABET_CHARCTERS]={'a','b'};

int Transition_Table[TOTAL_STATES][ALPHABET_CHARCTERS];

int Current_state=q0;

void DefineDFA()

{

    Transition_Table[q0][a] = q1;

    Transition_Table[q0][b] = q0;

    Transition_Table[q1][a] = q1;

    Transition_Table[q1][b] = q0;

}

int DFA(char current_symbol)

{

int i,pos;

    for(pos=0;pos<ALPHABET_CHARCTERS; pos++)

        if(current_symbol==alphabet[pos])   

            break;//stops if any character other than a or b

    if(pos==ALPHABET_CHARCTERS)

         return UNKNOWN_SYMBOL_ERR;

    for(i=0;i<FINAL_STATES;i++)

 if((Current_state=Transition_Table[Current_state][pos])

==Accepted_states[i])

            return REACHED_FINAL_STATE;

    return NOT_REACHED_FINAL_STATE;

}

int main(void)

{

    char current_symbol;

    int result;

    DefineDFA();    //Fill transition table

    printf("Enter a string with 'a' s and 'b's:\n

                Press Enter Key to stop\n");

    while((current_symbol=getchar())!= '\n')

        if((result= DFA(current_symbol))==UNKNOWN_SYMBOL_ERR)

            break;

    switch (result) {

    case UNKNOWN_SYMBOL_ERR:printf("Unknown Symbol %c",

  current_symbol); 

 break;

    case NOT_REACHED_FINAL_STATE:printf("Not accepted"); break;

    case REACHED_FINAL_STATE:printf("Accepted");break;

    default: printf("Unknown Error");

    }

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

    return 0;

}

OUTPUT
========

String with only "a"s and "b"s and last symbol is "a".     ACCEPTED..!!

String with only "a"s and "b"s but  last symbol is not  "a".     REJECTED..!!

Unknown symbol "y" in input. REJECTED.!!!!

Posted in: C PROGRAMS , Language processing programs