finite-automata - 我可以在图灵机中使用堆栈吗？

Question

我正在尝试设计一个接受语言 L = {w | 的图灵机 a ⁿ b ²ⁿ } 其中 ∑ = {a, b}。

例如机器接受输入：“aabbbb”但不接受“aabb”

我的代码在下面关于该语言；

#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;
}

问题是：这是一台图灵机吗？或者我可以在图灵机中使用堆栈吗？

谢谢

Answer 1

您可以使用堆栈。

首先，假设您使用了图灵机，并在其中添加了另一条轨道。显然，可以将附加轨道用于堆栈。

但是多轨图灵机相当于图灵机，有一种机械的方式将前者转化为后者。所以堆栈轨道可以折叠成一个普通的图灵机。