DFA for string pattern ab*cb* and Implementation of DFA in C program

Formal definition of Deterministic finite automaton (DFA)

A Deterministic finite automaton M is a 5-tuple (Q, Σ, δ, q₀, F ) where

1. Q is a finite set of states called the states,
2. Σ is a finite set of input symbols called the alphabet,
3. δ: Q x Σ→Q is the transition function
4. q₀ ∈ Q is the start state, and
5. F ⊆Q is the set of accept states.

DFA for the string pattern ab*cb*

Complete State Diagram:

Here,

1. Q= {q₁, q₂, q₃, q₄}

2. Σ= {a, b, c}

    Σ*= {ac, abc, acb, abcb, abbcbb, abbbcbbb, abcbbb, abbbcb…………}

3. q₀=  q₁∈  Q

4. F= {q₃}⊆ Q

Transition Table:

CurrentStates \ Input	a	b	c
q1	q2	q4	q4
q2	q4	q2	q3
q3	q4	q3	q4

Implementation using C program:

#include<stdio.h>

#define EOS '\0'

int main()

{

    char c, inpstr[50];

    int i, q;

    printf("Enter String: ");

    scanf("%s",inpstr);

    q=1;

    i=0;

    c=inpstr[i];

    printf("\n");

    printf("%s ", inpstr);

    while(c!=EOS)

    {

         if(q==1 && c=='a')

        {

            q=2;

        }

        else if(q==2 && c=='b')

        {

            q=2;

        }

        else if(q==2 && c=='c')

        {

            q=3;

        }

        else if(q==3 && c=='b')

        {

            q=3;

        }

        else

        {

            q=4;

            break;

        }

        i++;

        c=inpstr[i];

    }

    if(q==4)

        printf("    Illegal");

    else

        printf("    Legal");

    printf("\n");

    return 0;

}