finite-automataautomataturing-machinesautomata-theory

Can I use stack in Turing Machine?


I am trying to design a Turing Machine that accepts the language L = {w | anb2n} where ∑ = {a, b}.

For example machine accepts the input : "aabbbb" but does not accept the "aabb"

My code is below about that language ;

#include <iostream>
#include <string>
using namespace std;

char stack[30];
int top = -1;

void push(char ch){
    stack[++top] = ch;
}

char pop(){
    return stack[top--];
}

int main(){
    string str;
    char flag = 0;
    cout<<"Enter input string: ";
    cin>>str;

    for(int i=0; i<str.length(); i++){      
        if(str[i] == 'a')
            push(str[i]);

        else if(str[i] == 'b'){
            if(top<0 || i>=str.length()-1 || str[++i] != 'b'){
                flag = 1;
                break;
            }
            pop();          
        }

        else{
            flag = 1;
            break;
        }
    }

    if(flag == 1 || top != -1)
        cout<<"Input unacceptable by turing machine.\n";
    else
        cout<<"Input acceptable by turing machine.\n";
    system("PAUSE");
    return 0;
}

The question is : is this a Turing Machine ? or can I use stack in Turing Machine ?

Thank you


Solution

  • You can use a stack.

    To begin with, suppose you took your Turing machine, and added to it another track. Clearly, it is is possible to use the additional track for the stack.

    However, a multitrack Turing machine is equivalent to a Turing machine, and there is a mechanical way to transform the former to the latter. So the stack-track can be folded into a regular Turing machine.