Машина Тьюринга. Перенос нуля. Реализировать на С++

@Asuser · Регистрация: 22.10.2012

Author24 — интернет-сервис помощи студентам

Приветствую! Я в С++ очень плохо разбираюсь, но нужна программа... Буду рад всем откликнувшимся.

@Asuser · 24.10.2012, 22:57 **[ТС]**

C++

#include <iostream>
#include <conio.h>
using namespace std;
 
int main()
{
    int q,n,i;
    char a[20];
 
    cout << "Vvedit slovo (alfavit {0,1}): ";
    cin >> a;
    
    i=0;
    q=1;
    
    while(q!=0)
    {
        if (a[i]=='0')
        {
            switch(q)
            {
            case 1: { a[i]='0'; q=2; i++; break; }
            case 2: { cout<<a<<endl; a[i]='1'; q=3; break; }
            case 3: { cout<<a<<endl; a[i]='0'; q=4; i--; break; }
            case 4: { cout<<a<<endl; a[i]='0'; q=6; i--; break; }
            case 5: { cout<<a<<endl; a[i]='0'; q=0; break; }    
            }
        }
        else if (a[i]=='1')
        {
            switch(q)
            {
            case 1: { cout<<a<<endl; a[i]='1'; q=3; i++; break; }
            case 2: { cout<<a<<endl; a[i]='0'; q=5; break;}
            case 3: { cout<<a<<endl; a[i]='1'; q=6; i--; break; }
            }
        }
    }
    cout << "\nVihidne slovo: "<<a;
getch();
}

Машина Тьюринга. Перенос нуля. Реализировать на С++

Не работает, исправьте, кто может...

@doctor_lecter · 24.10.2012, 23:48

Не очень понял что у вас в задании. Могу привести пример примитивной реализации машины Тьюринга, вы для нее можете попробовать задать правила для своего задания. На этом примере я реализовал машину Тьюринга, которая заменяет 0 на 1 и наоборот. Могут быть баги, сделал только что и тестил только на этом примере:

C++

#include <iostream>
 
using namespace std;
 
struct rule {
    char input;     // Входной символ '\0' - последний
    char state;     // Состояние. 'S' - начальное. 'Q' - завершение работы
    char output;    // Выходной символ
    char newState;  // Новое состояние
    char dir;       // Направление движения. 'L', 'R' - налево и направо соответственно. 'N' - не двигаться
};
 
bool turing(
    char* arr,      // Входная лента. Для простоты пусть будет конечной длины
    int len,        // Длина ленты
    rule* rules,    // Список правил
    int num         // Количество правил
) {
    int pos = 0;    // Положение ленты
    char st = 'S';  // Текущее состояние
    while (true) {
        char c = arr[pos];
        int i;
        for (i=0; i < num; ++i) {
            if ((rules[i].input==c) && (rules[i].state == st))
                break;
            else
                if (i == num-1) {
                    cout << "Не найдено правила для символа " << c << " при состоянии " << st << endl;
                    return false;
                }
        }
        arr[pos] = rules[i].output;
        st = rules[i].newState;
        switch (rules[i].dir) {
        case 'L':
            --pos;
            if (pos < 0) {
                cout << "Выход за пределы ленты слева" << endl;
                return false;
            }
            break;
        case 'R':
            ++pos;
            if (pos >= len) {
                cout << "Выход за пределы ленты справа" << endl;
                return false;
            }
            break;
        case 'N':
            break;
        default:
            cout << "Неопределенное направление" << endl;
            return false;
        }
        if (st == 'Q')
            return true;
    }
    return false;
}
 
int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 3;
    rule rules[3];
    rules[0].input = '0';
    rules[0].state = 'S';
    rules[0].output = '1';
    rules[0].newState = 'S';
    rules[0].dir = 'R';
    rules[1].input = '1';
    rules[1].state = 'S';
    rules[1].output = '0';
    rules[1].newState = 'S';
    rules[1].dir = 'R';
    rules[2].input = '\0';
    rules[2].state = 'S';
    rules[2].output = '\0';
    rules[2].newState = 'Q';
    rules[2].dir = 'N';
 
    const int size = 6;
    char test[6] = {'1', '0', '0', '1', '1', '\0'};
 
    cout << "Входная лента:";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента: ";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        return 0;
    } else {
        cout << endl << "Ошибка" << endl;
        return 1;
    }
}

@Asuser · 25.10.2012, 11:03 **[ТС]**

doctor_lecter, нужен перенос нуля. Например ввели слово 0010, после обработки командами МТ на выходе имеем 0100. Было 0111100, стало 0011110. Вот впринципе и все

Дело в том, что тот набор команд 100% правильный (во втором посте), наверняка закодил неправильно...

@doctor_lecter · 25.10.2012, 11:30

Обычно набор команд МТ имеет вид: Входной символ|состояние -> Выходной символ|Состояние|Направление, а у вас после -> идет Состояние и Либо выходной символ, либо направление. Это в принципе тоже правильно, просто получится менее компактно.

Я правильно понял что входное слово имеет такой вид: 000001..{тут не может быть 0}...10000

Тогда функцию main можно написать так:

C++

int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 7;
    rule rules[ruleNum];
 
    rules[0].input = '0';
    rules[0].state = 'S';
    rules[0].output = '0';
    rules[0].newState = 'A';
    rules[0].dir = 'N';
 
    rules[1].input = '0';
    rules[1].state = 'A';
    rules[1].output = '0';
    rules[1].newState = 'A';
    rules[1].dir = 'R';
 
    rules[2].input = '1';
    rules[2].state = 'A';
    rules[2].output = '1';
    rules[2].newState = 'B';
    rules[2].dir = 'L';
 
    rules[3].input = '0';
    rules[3].state = 'B';
    rules[3].output = '1';
    rules[3].newState = 'C';
    rules[3].dir = 'R';
 
    rules[4].input = '1';
    rules[4].state = 'C';
    rules[4].output = '1';
    rules[4].newState = 'C';
    rules[4].dir = 'R';
 
    rules[5].input = '0';
    rules[5].state = 'C';
    rules[5].output = '0';
    rules[5].newState = 'D';
    rules[5].dir = 'L';
 
    rules[6].input = '1';
    rules[6].state = 'D';
    rules[6].output = '0';
    rules[6].newState = 'Q';
    rules[6].dir = 'N';
 
    const int size = 10;
    char test[size] = {'0', '0', '0', '1', '1', '0', '\0', '\0', '\0', '\0'};
 
    cout << "Входная лента: ";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента:";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        return 0;
    } else {
        cout << "Ошибка" << endl;
        return 1;
    }
}

Это вариант отработает и на входных данных вида 00011010, на выходе будет 00110010, т.е будет перенесен только 0 у первой последовательности 1

@kira_1 · 02.06.2014, 21:26

Подскажите, пожалуйста, в чем ошибка. По этому примеру сделала МТ, которая выполняет умножение 2 чисел в унарной системе. Пишет, что для определенного символа правила, а по алфавиту все правильно введено.

Вот алфавит:

q0*→q0R q4a→q4aR
q01→q0R q4=→q4=R
q0×→q1×R q41→q41R
q11→q2aR q4*→q51R
q21→q21L q5*→q2*L
q2a→q2aL q6a→q61R
q2=→q2=L q6×→q7×R
q2×→q3×L q7a→q7aR
q31 → q4aR q71→q2aR
q3a→q3aL q7=→q8=L
q3*→q6*R q8a→q81L
q4×→q4×R q8×→q9H

А вот код программы:

C++

#include <iostream>
 
using namespace std;
#include <conio.h>;
struct rule {
    char input;     // Входной символ '\0' - последний
    char state;     // Состояние. 'S' - начальное. 'Q' - завершение работы
    char output;    // Выходной символ
    char newState;  // Новое состояние
    char dir;       // Направление движения. 'L', 'R' - налево и направо соответственно. 'N' - не двигаться
};
 
bool turing(
    char* arr,      // Входная лента. Для простоты пусть будет конечной длины
    int len,        // Длина ленты
    rule* rules,    // Список правил
    int num         // Количество правил
) {
    int pos = 0;    // Положение ленты
    char st = 'A';  // Текущее состояние
    while (true) {
        char c = arr[pos];
        int i;
        for (i=0; i < num; ++i) {
            if ((rules[i].input==c) && (rules[i].state == st))
                break;
            
            else
                if (i == num-1) {
                    cout << "Не найдено правила для символа " << c << " при состоянии " << st << endl;
                    return false;
                }
 
        }
        arr[pos] = rules[i].output;
        st = rules[i].newState;
        switch (rules[i].dir) {
        case 'L':
            --pos;
            if (pos < 0) {
                cout << "Выход за пределы ленты слева" << endl;
                return false;
            }
            break;
        case 'R':
            ++pos;
            if (pos >= len) {
                cout << "Выход за пределы ленты справа" << endl;
                return false;
            }
            break;
        case 'N':
            break;
        default:
            cout << "Неопределенное направление" << endl;
            return false;
        }
        if (st == 'Q')
            return true;
    }
    return false;
}
int main() {
    setlocale(LC_ALL, "Russian");
 
    const int ruleNum = 24;
    rule rules[ruleNum];
 
    rules[0].input = '*';
    rules[0].state = 'A';
    rules[0].newState = 'A';
    rules[0].dir = 'R';
 
    rules[1].input = '1';
    rules[1].state = 'A';
    rules[1].newState = 'A';
    rules[1].dir = 'R';
 
    rules[2].input = 'x';
    rules[2].state = 'A';
    rules[2].output = 'x';
    rules[2].newState = 'B';
    rules[2].dir = 'R';
 
    rules[3].input = '1';
    rules[3].state = 'B';
    rules[3].output = 'a';
    rules[3].newState = 'C';
    rules[3].dir = 'R';
 
    rules[4].input = '1';
    rules[4].state = 'C';
    rules[4].output = '1';
    rules[4].newState = 'C';
    rules[4].dir = 'L';
 
    rules[5].input = 'a';
    rules[5].state = 'C';
    rules[5].output = 'a';
    rules[5].newState = 'C';
    rules[5].dir = 'L';
 
    rules[6].input = '=';
    rules[6].state = 'C';
    rules[6].output = '=';
    rules[6].newState = 'C';
    rules[6].dir = 'L';
 
    rules[7].input = 'x';
    rules[7].state = 'C';
    rules[7].output = 'x';
    rules[7].newState = 'D';
    rules[7].dir = 'L';
 
    rules[8].input = '1';
    rules[8].state = 'D';
    rules[8].output = 'a';
    rules[8].newState = 'E';
    rules[8].dir = 'R';
 
    rules[9].input = 'a';
    rules[9].state = 'D';
    rules[9].output = 'a';
    rules[9].newState = 'D';
    rules[9].dir = 'L';
 
    rules[10].input = '*';
    rules[10].state = 'D';
    rules[10].output = '*';
    rules[10].newState = 'J';
    rules[10].dir = 'R';
 
    rules[11].input = 'x';
    rules[11].state = 'E';
    rules[11].output = 'x';
    rules[11].newState = 'E';
    rules[11].dir = 'R';
 
    rules[12].input = 'a';
    rules[12].state = 'E';
    rules[12].output = 'a';
    rules[12].newState = 'E';
    rules[12].dir = 'R';
 
    rules[13].input = '=';
    rules[13].state = 'E';
    rules[13].output = '=';
    rules[13].newState = 'E';
    rules[13].dir = 'R';
 
    rules[14].input = '1';
    rules[14].state = 'E';
    rules[14].output = '1';
    rules[14].newState = 'E';
    rules[14].dir = 'R';
 
    rules[15].input = '*';
    rules[15].state = 'E';
    rules[15].output = '1';
    rules[15].newState = 'F';
    rules[15].dir = 'R';
 
    rules[16].input = '*';
    rules[16].state = 'F';
    rules[16].output = '*';
    rules[16].newState = 'C';
    rules[16].dir = 'L';
 
    rules[17].input = 'a';
    rules[17].state = 'J';
    rules[17].output = '1';
    rules[17].newState = 'J';
    rules[17].dir = 'R';
 
    rules[18].input = 'x';
    rules[18].state = 'H';
    rules[18].output = 'x';
    rules[18].newState = 'I';
    rules[18].dir = 'R';
 
    rules[19].input = 'a';
    rules[19].state = 'H';
    rules[19].output = 'a';
    rules[19].newState = 'H';
    rules[19].dir = 'R';
 
    rules[20].input = '1';
    rules[20].state = 'H';
    rules[20].output = 'a';
    rules[20].newState = 'C';
    rules[20].dir = 'R';
 
    rules[21].input = '=';
    rules[21].state = 'H';
    rules[21].output = '=';
    rules[21].newState = 'I';
    rules[21].dir = 'L';
 
    rules[22].input = 'a';
    rules[22].state = 'I';
    rules[22].output = '1';
    rules[22].newState = 'I';
    rules[22].dir = 'L';
 
    rules[23].input = 'x';
    rules[23].state = 'I';  
    rules[23].newState = 'Q';
    rules[23].dir = 'N';
 
 
    const int size = 8;
    char test[size] = {'*', '1', '1', '1', 'x', '1', '1', '*'};
 
    cout << "Входная лента: ";
    for (int i=0; i < size; ++i)
        cout << ' ' << test[i];
    if (turing(test, size, rules, ruleNum)) {
        cout << endl << "Выходная лента:";
        for (int i=0; i < size; ++i)
            cout << ' ' << test[i];
        cout << endl;
        getch();
        return 0;
    } else {
        cout << "Ошибка" << endl;
            getch();
        return 1;
    }
}

@Asuser 0 / 0 / 0 Регистрация: 22.10.2012 Сообщений: 18
		1
	Машина Тьюринга. Перенос нуля. Реализировать на С++ 22.10.2012, 23:17. Показов 12536. Ответов 5 Метки нет (Все метки) Приветствую! Я в С++ очень плохо разбираюсь, но нужна программа... Буду рад всем откликнувшимся. Миниатюры 0

@Asuser 0 / 0 / 0 Регистрация: 22.10.2012 Сообщений: 18
	25.10.2012, 11:03 [ТС]	4
	doctor_lecter, нужен перенос нуля. Например ввели слово 0010, после обработки командами МТ на выходе имеем 0100. Было 0111100, стало 0011110. Вот впринципе и все Дело в том, что тот набор команд 100% правильный (во втором посте), наверняка закодил неправильно... 0

	02.06.2014, 21:26