Program for Turing Machine capable of recognizing the language 1^n0^n where n>0

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, q4}
  2. Σ= {0, 1}
  3. Γ= {0, 1, X, Y, B}
  4. qs= q0
  5. qaccept = {q4}
  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]=='1')
            {
                state=1;
                inpstr[head++]='X';
            }
            else if(inpstr[head]=='Y')
            {
                state=3;
                inpstr[head++]='Y';
            }
            else
            {
                state=5;
                break;
            }
        }
        else if(state==1)
        {
            if(inpstr[head]=='1')
            {
                state=1;
                inpstr[head++]='1';
            }
            else if(inpstr[head]=='Y')
            {
                state=1;
                inpstr[head++]='Y';
            }
            else if(inpstr[head]=='0')
            {
                state=2;
                inpstr[head--]='Y';
            }
            else
            {
                state==5;
                break;
            }
        }
        else if(state==2)
        {
            if(inpstr[head]=='1')
            {
                state=2;
                inpstr[head--]='1';
            }
            else if(inpstr[head]=='Y')
            {
                state=2;
                inpstr[head--]='Y';
            }
            else if(inpstr[head]=='X')
            {
                state=0;
                inpstr[head++]='X';
            }
            else
            {
                state=5;
                break;
            }
        }
        else if(state==3)
        {
            if(inpstr[head]=='Y')
            {
                state=3;
                inpstr[head++]='Y';
            }
            else if(inpstr[head]==BlankSpace)
            {
                state=4;
                inpstr[head]=BlankSpace;
                break;
            }
            else
            {
                state=5;
                break;
            }
        }
        else
        {
            state=5;
            break;
        }
    }

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

    printf("\n");

    return 0;
}




I/O:

Input: 11110000
Output: Accepted

Input: 000111
Output: Rejected

Input: 111100
Output: Rejected

Comments

Post a Comment