0

言語 L = {w | w を受け入れるチューリング マシンを設計しようとしています。a n b 2n } ここで、∑ = {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;
}

問題は、これはチューリングマシンですか? または、チューリングマシンでスタックを使用できますか?

ありがとうございました

4

1 に答える 1

2

スタックを使用できます。

まず、チューリング マシンに別のトラックを追加したとします。スタックに追加のトラックを使用できることは明らかです。

ただし、マルチトラック チューリング マシンはチューリング マシンと同等であり、前者を後者に変換する機械的な方法があります。したがって、スタック トラックは通常のチューリング マシンに折りたたむことができます。

于 2015-05-29T14:20:50.130 に答える