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
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.