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

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

您可以使用堆栈。

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

不过，多轨图灵机是equivalent到图灵机，并且有一种机械方式可以将前者转换为后者。所以stack-track可以折叠成一个普通的图灵机。

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

Can I use stack in Turing Machine?

finite-automata

automata

turing-machines

automata-theory