Program for Turing Machine to accept string of language given by pattern ab*c

Formal definition of Turing Machine (TM)

A Turing machine is a 7-tuple, (Q, Σ, Γ, δ, q0, qaccept, qreject), where
Q, Σ, Γ are all finite sets and

1. Q is the set of states,
2. Σ is the input alphabet not containing the blank symbol B,
3. Γ is the tape alphabet, where B ∈ Γ and Σ ⊆ Γ,
4. δ: Q × Γ→Q × Γ × {L, R} is the transition function,
5. q0 ∈ Q is the start state,
6. qaccept ∈ Q is the accept state, and
7. qreject ∈ Q is the reject state, where qreject != qaccept.

State Diagram


Here,
  1. Q= {q0, q1, q2, q3}
  2. Σ= {a, b, c}
  3. Γ= {a, b, c, B}
  4. qs= q0
  5. qaccept = {q3}
  6. qreject = { Ø }
  7. δ is given by the following transition table
Transition Table:



Program

#include<stdio.h>
#define BlankSpace '\0'

int main()
{
    char inpstr[50];
    int head, state;
    printf("Enter String: ");
    scanf("%s",inpstr);
    state=0;
    head=0;
    printf("\n");
    printf("%s ", inpstr);
    while(1)
    {
         if(state==0)
        {
            if(inpstr[head]=='a')
            {
                state=1;
                inpstr[head++]='a';
            }
            else
            {
                state=4;
                break;
            }
        }
        else if(state==1)
        {
            if(inpstr[head]=='b')
            {
                state=1;
                inpstr[head++]='b';
            }
            else if(inpstr[head]=='c')
            {
                state=2;
                inpstr[head++]='c';
            }
            else
            {
                state==4;
                break;
            }
        }
        else if(state==2)
        {
            if(inpstr[head]==BlankSpace)
            {
                state=3;
                inpstr[head++]=BlankSpace;
                break;
            }
            else
            {
                state=4;
                break;
            }
        }
        else
        {
            state=4;
            break;
        }
    }

    if(state==3)
        printf("    Accepted");
   else
        printf("    Rejected");

    printf("\n");

    return 0;
}


I/O:

Input: ac
Output: Accepted

Input: abbbbbbbbbbc
Output: Accepted

Input: abbcc
Output: Rejected

Input: abcd
Output: Rejected

Comments

Post a Comment