Машина Тьюринга: не хватает одного IF в программе

@Aliksan · Регистрация: 22.09.2015

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

Добрый день.
Программа считывает вводимый мной файл (1.txt, 2.txt, 3.txt, 4.txt). Считываются положение головки, самой полосы данных и инструкции.
Программа работает со всеми, кроме 1.txt

C++

#include <iostream>
#include <string>
#include <fstream>
 
using namespace std;
 
int main()
{
    const int MAX = 100;
    
    int  header;
    int i = 0;
    int j = 0;
    int star;
 
    bool stop = 0;
    bool starexist = 0;
    bool exist = 0;
 
    char current_symbol[MAX];
    char new_symbol[MAX];
    char direction[MAX];
 
    string line;
    string filename;
    string chars = "RL*";
    string current_status[MAX];
    string new_status[MAX];
    string temp;
 
    cout << "Enter file name:" << endl;
    cin >> filename;
    ifstream object(filename.c_str());
 
    if (!object) {
        cerr << "Error, the file " << filename << " does not exist!"  << endl;
    return -1;
    }
 
    object >> header;
    header--;
    object >> line;
    
    while (!object.eof()) {
        object >> current_status[i] >> current_symbol[i] >> new_symbol[i] >> direction[i] >> new_status[i];
        i++;
    }
 
    object.close();
 
    temp = current_status[0];
    
    for (j = 0; j <= i; j++) {
        starexist = 0;
        exist = 0;
        if (current_status[j] == temp) {
            if (current_symbol[j] == chars[2]) {
                if (current_symbol[j] == line[header]) {
                    exist = 1;
                        line[header] = new_symbol[j];
                        if (direction[j] == chars[0]) header++;
                        if (direction[j] == chars[1]) header--;
                        if (direction[j] == chars[2]) header = header;
 
                    cout << line << endl;
                    temp = new_status[j];
                    j = -1;
                }
 
                else {
                    star = j;
                    j++;
                    starexist = 1;
                }
 
            }
 
            if (exist == 0 && current_symbol[j] == line[header]) {
                exist = 1;
                line[header] = new_symbol[j];
 
                if (direction[j] == chars[0]) header++;
                if (direction[j] == chars[1]) header--;
                if (direction[j] == chars[2]) header = header;
                cout << line << endl;
                temp = new_status[j];
                j = -1;
            }
        }
 
        if ((j == i) && (exist == 0)) {
            if (starexist == 1) {
                line[header] = new_symbol[star];
                if (direction[star] == chars[0]) header++;
                if (direction[star] == chars[1]) header--;
                if (direction[star] == chars[2]) header = header;
                cout << line << endl;
                temp = new_status[star];
                j = -1;
            }
 
            else {
                stop = 1;
                j = i + 1;
            }
 
        }
    }
    if (stop == 1) cout << "Finished!" << endl;
return 0;
}

Вот содержание 1.txt

C++

1
00V0000000001111*A000000000001111*B000000000000000000000000ZR000000000H000000
 
0 0 0 R 0
0 1 1 R 0
0 V V R 0 
0 * * L 1
 
1 0 * R 2
1 1 * R 3
1 V V R 20
1 V V R 20
 
2 * 0 R 4
3 * 1 R 5
 
4 A A R 4
4 0 0 R 4
4 1 1 R 4
5 A A R 5
5 0 0 R 5
5 1 1 R 5
 
4 * * L 6
5 * * L 7
 
6 0 * R 8
6 1 * R 9
7 0 * R 10
7 1 * R 11
6 A A R 20
7 A A R 20
 
8 * 0 R 12
9 * 1 R 13
10 * 0 R 14
11 * 1 R 15
 
12 B B R 12
12 0 0 R 12
12 1 1 R 12
13 B B R 13
13 0 0 R 13
13 1 1 R 13
14 B B R 14
14 0 0 R 14
14 1 1 R 14
15 B B R 15
15 0 0 R 15
15 1 1 R 15
 
12 Z 0 L 16
13 Z 1 L 16
14 Z 1 L 16
15 Z 0 L 17
 
12 C 1 L 16
13 C 0 L 17
14 C 0 L 17
15 C 1 L 17
 
16 0 Z L 18
17 0 C L 18
 
18 A A L 18
18 B B L 18
18 * * L 18
18 0 0 L 18
18 1 1 L 18
18 V V R 0
 
20 A A R 20
20 B B R 20
20 * * R 20
20 0 0 R 20
20 1 1 R 20
20 Z 0 R 21
20 C 1 R 21
 
21 0 0 R X
21 1 1 R X

Программа дает такой результат;

C++

1	00V0000000001111A000000000001111B0000000000000000000011110R000000000H000000

А должно быть так;

C++

1	00V0000000001111110000000000011111100000000000000000000000100000000000H000000

Помогите

@Max Dark · 04.10.2016, 12:14

Aliksan, можете выложить остальные входные файлы?

Bash

$> clang++ -std=c++11 -Wall -Wpedantic -Wextra -Werror -mtune=native -c machine.cpp
machine.cpp:63:62: error: explicitly assigning value of variable of type 'int' to itself [-Werror,-Wself-assign]
                        if (direction[j] == chars[2]) header = header;
                                                      ~~~~~~ ^ ~~~~~~
machine.cpp:84:54: error: explicitly assigning value of variable of type 'int' to itself [-Werror,-Wself-assign]
                if (direction[j] == chars[2]) header = header;
                                              ~~~~~~ ^ ~~~~~~
machine.cpp:96:57: error: explicitly assigning value of variable of type 'int' to itself [-Werror,-Wself-assign]
                if (direction[star] == chars[2]) header = header;

@Aliksan · 04.10.2016, 21:08 **[ТС]**

Остальные файлы;
2.txt

C++

7
00000000000000000000000*0000
0 0 0 R 0
0 1 1 R 0
0 * * L 1
1 0 1 R 0
1 1 0 L 1

3.txt

C++

7
00000000000000000000000*0000
 
0 0 0 R 0
0 1 1 R 0
0 2 2 R 0
0 3 3 R 0
0 4 4 R 0
0 5 5 R 0
0 6 6 R 0
0 7 7 R 0
0 8 8 R 0
0 9 9 R 0
 
0 * * L 1
 
1 0 1 R 0
1 1 2 R 0
1 2 3 R 0
1 3 4 R 0
1 4 5 R 0
1 5 6 R 0
1 6 7 R 0
1 7 8 R 0
1 8 9 R 0
1 9 0 L 1

4.txt

C++

7
000100000000000000001111111000000000000000010000
0 0 0 R 0
0 1 0 R 11
11 1 1 R 11
11 0 1 R 2
2 0 0 L 3
2 1 1 L 4
3 1 1 L 3
3 0 0 R 0
4 1 0 L 5
4 0 0 L 4
5 1 1 L 5
5 0 1 L 12
12 0 0 R 6
12 1 1 R 0
6 1 1 R 6
6 0 0 L 4

Добавлено через 1 минуту
Программа компилируется без ошибок и запускается в linux через g++.

Добавлено через 3 минуты
Для Windows, скорее всего надо поменять эту строчку

C++

1	ifstream object(filename.c_str());

на эту;

C++

1	ifstream object(filename);

@Max Dark · 05.10.2016, 04:42

Aliksan, а в самом файле 1.txt случайно нет ошибки?

моя реализация

C++

/**
 * @file machine.cpp
 * @compile g++ -std=c++11 -Wall -Wpedantic -Wextra -Werror -O2 -mtune=native machine.cpp -o machine
 * */
 
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <map>
 
namespace tools {
    std::string right_trim(const std::string &str) noexcept {
        std::string::size_type last_space = str.find_last_not_of(" \t\r\n");
        return last_space == std::string::npos ? "" : (
                str.size() == (last_space + 1) ? str : str.substr(0, last_space + 1)
        );
    }
}
 
namespace turing {
    /**
     * direction constants
     */
    enum directions {
        RIGHT = 'R',
        LEFT  = 'L',
        SAME  = '*'
    };
    template<typename T1, typename T2>
    using map = std::map<T1, T2>;
    using state_type = std::string;
    using symbol_type = char;
 
    /**
     * next state for turing::machine
     */
    struct next_state {
        /**
         * move direction
         */
        symbol_type direction;
        /**
         * next state
         */
        state_type next_state;
        /**
         * replace symbol
         */
        symbol_type next_char;
    };
 
    using state_list = map<symbol_type, next_state>;
    using state_map = map<state_type, state_list>;
 
    /**
     * machine state
     */
    struct machine {
        /**
         * current head position
         */
        size_t head_position;
        /**
         * current state
         */
        state_type state;
        /**
         * machine "tape"
         */
        std::string tape;
        /**
         * state table
         */
        state_map state_table;
    };
 
    /**
     * load machine state from input stream
     * 
     * @param input stream 
     * @return loaded state
     * @throw std::runtime_error if cant parse state line
     */
    machine load(std::istream& input) throw(std::runtime_error) {
        machine m;
        std::string line;
 
        input >> m.head_position;
        input >> m.tape;
 
        while (std::getline(input, line)) {
            line = tools::right_trim(line);
            if (line.empty())
                continue;
            std::istringstream parser(line);
            state_type current_state, next_state;
            symbol_type current_char, next_char, direction;
 
            parser >> current_state >> current_char >> next_char >> direction >> next_state;
            if (parser.fail()) {
                throw std::runtime_error("parser.fail()");
            }
            // fill state for current state+char pair
            {
                auto& state = m.state_table[current_state][current_char];
                state.direction  = direction;
                state.next_char  = next_char;
                state.next_state = next_state;
            }
        }
        m.state = m.state_table.begin()->first;
        m.tape = tools::right_trim(m.tape);
        --m.head_position;
        return m;
    }
 
    /**
     * run machine
     * @param m machine state
     * @return 0
     * @throw std::runtime_error if cant find next state
     * @throw std::out_of_range if head outside tape
     */
    int run(machine& m) throw(std::runtime_error, std::out_of_range) {
        bool in_cycle = false;
        bool stop = false;
 
        while (!stop) {
            state_map::iterator state;
            state_list::iterator next;
 
            // find state table for current state
            state = m.state_table.find(m.state);
            if (state == m.state_table.end()) {
                // m.state missing in m.state_table
                throw std::runtime_error("state == m.state_table.end()");
            }
            // find next state for current symbol
            const auto current_symbol = m.tape.at(m.head_position);
            next = state->second.find(current_symbol);
            if (next == state->second.end()) {
                // current_symbol missing in m.state_table[m.state]
                throw std::runtime_error("next == state->second.end()");
            }
            next_state new_state = next->second;
            m.tape[m.head_position] = new_state.next_char;
            m.state = new_state.next_state;
 
            switch (new_state.direction) {
                case RIGHT:
                    in_cycle = false;
                    m.head_position++;
                    break;
                case LEFT:
                    in_cycle = false;
                    m.head_position--;
                    break;
                case SAME:
                    if (in_cycle) {
                        throw std::runtime_error("loop detected");
                    }
                    in_cycle = true;
                    break;
                default:
                    throw std::runtime_error("wrong direction");
            }
            std::cout << m.tape << std::endl;
            stop = m.state == "X";
        }
        return 0;
    }
}
 
int main(int argc, char** argv) {
    std::string file_name;
    std::ifstream input;
 
 
    if (argc == 1) {
        std::cout << "Enter file name > ";
        std::cin >> file_name;
    } else {
        file_name = argv[1];
    }
 
    input.open(file_name);
 
    if (!input.is_open()) {
        std::cerr << "open fail" << std::endl;
        return 0xdead;
    }
    try
    {
        using namespace turing;
        machine m = load(input);
        return run(m);
    }
    catch (std::runtime_error& e) {
        std::cerr << "Aborted: " << e.what() << std::endl;
    }
    return 0xdead;
}

выдает

Код

00V*0000000001111A00*0000000001111B0000000000000000000011110R000000000H00000

@Aliksan · 05.10.2016, 15:56 **[ТС]**

Очень сложно у вас написано, сразу чувствуется, что код писал не любитель программирования и даже не студент...
Буду смотреть ваш код. 1.тхт тестировался тут. И результат без знаков умножения и букв A, B, C.

Добавлено через 6 минут
Один студент сказал, что проблему решил после того, как отсортировал инструкции. Я взял и сортировку сделал не в коде а в 1.тхт, естественно, проблему это не решило.

Добавлено через 19 минут
Только что проверил ваш код на работоспособность, та же история ... 1.тхт тупит. Пытался подрихтовать сам 1.тхт, удалить пару тройку инструкций, кой-что изменить, но в итоге это еще сложнее, чем подправить код.

@Max Dark · 05.10.2016, 16:25

Сообщение от Aliksan

1.тхт тестировался тут.

переделал под те правила:

* в текущем символе означает "любой символ"
* в следующем символе означает "оставить как есть"

теперь выдает

Код

00V0000000001111110000000000011111100000000000000000000000100000000000H000000

реализация

C++

/**
 * @file machine.cpp
 * @compile g++ -std=c++11 -Wall -Wpedantic -Wextra -Werror -O2 -mtune=native machine.cpp -o machine
 * */
 
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <map>
 
namespace tools {
    std::string right_trim(const std::string &str) noexcept {
        std::string::size_type last_space = str.find_last_not_of(" \t\r\n");
        return last_space == std::string::npos ? "" : (
                str.size() == (last_space + 1) ? str : str.substr(0, last_space + 1)
        );
    }
}
 
namespace turing {
    /**
     * direction constants
     */
    enum directions {
        RIGHT = 'R',
        LEFT  = 'L',
        SAME  = '*'
    };
    template<typename T1, typename T2>
    using map = std::map<T1, T2>;
    using state_type = std::string;
    using symbol_type = char;
 
    /**
     * next state for turing::machine
     */
    struct next_state {
        /**
         * move direction
         */
        symbol_type direction;
        /**
         * next state
         */
        state_type next_state;
        /**
         * replace symbol
         */
        symbol_type next_char;
    };
 
    using state_list = map<symbol_type, next_state>;
    using state_map = map<state_type, state_list>;
 
    /**
     * machine state
     */
    struct machine {
        /**
         * current head position
         */
        size_t head_position;
        /**
         * current state
         */
        state_type state;
        /**
         * machine "tape"
         */
        std::string tape;
        /**
         * state table
         */
        state_map state_table;
    };
 
    /**
     * load machine state from input stream
     * 
     * @param input stream 
     * @return loaded state
     * @throw std::runtime_error if cant parse state line
     */
    machine load(std::istream& input) throw(std::runtime_error) {
        machine m;
        std::string line;
 
        input >> m.head_position;
        input >> m.tape;
 
        while (std::getline(input, line)) {
            line = tools::right_trim(line);
            if (line.empty())
                continue;
            std::istringstream parser(line);
            state_type current_state, next_state;
            symbol_type current_char, next_char, direction;
 
            parser >> current_state >> current_char >> next_char >> direction >> next_state;
            if (parser.fail()) {
                throw std::runtime_error("parser.fail()");
            }
            // fill state for current state+char pair
            {
                auto& state = m.state_table[current_state][current_char];
                state.direction  = direction;
                state.next_char  = next_char;
                state.next_state = next_state;
            }
        }
        m.state = m.state_table.begin()->first;
        m.tape = tools::right_trim(m.tape);
        --m.head_position;
        return m;
    }
 
    /**
     * run machine
     * @param m machine state
     * @return 0
     * @throw std::runtime_error if cant find next state
     * @throw std::out_of_range if head outside tape
     */
    int run(machine& m) throw(std::runtime_error, std::out_of_range) {
        bool in_cycle = false;
        bool stop = false;
 
        while (!stop) {
            state_map::iterator state;
            state_list::iterator next;
 
            // find state table for current state
            state = m.state_table.find(m.state);
            if (state == m.state_table.end()) {
                // m.state missing in m.state_table
                throw std::runtime_error("state == m.state_table.end()");
            }
            // find next state for current symbol
            const auto current_symbol = m.tape.at(m.head_position);
            next = state->second.find(current_symbol);
            if (next == state->second.end()) {
                // no rule for current_symbol, try find rule for "any" symbol
                next = state->second.find('*');
            }
            if (next == state->second.end()) {
                // current_symbol missing in m.state_table[m.state]
                throw std::runtime_error("next == state->second.end()");
            }
            next_state new_state = next->second;
            // no change if next char == '*'
            if (new_state.next_char != '*') {
                m.tape[m.head_position] = new_state.next_char;
            }
            m.state = new_state.next_state;
 
            switch (new_state.direction) {
                case RIGHT:
                    in_cycle = false;
                    m.head_position++;
                    break;
                case LEFT:
                    in_cycle = false;
                    m.head_position--;
                    break;
                case SAME:
                    if (in_cycle) {
                        throw std::runtime_error("loop detected");
                    }
                    in_cycle = true;
                    break;
                default:
                    throw std::runtime_error("wrong direction");
            }
            std::cout << m.tape << std::endl;
            stop = m.state == "X";
        }
        return 0;
    }
}
 
int main(int argc, char** argv) {
    std::string file_name;
    std::ifstream input;
 
 
    if (argc == 1) {
        std::cout << "Enter file name > ";
        std::cin >> file_name;
    } else {
        file_name = argv[1];
    }
 
    input.open(file_name);
 
    if (!input.is_open()) {
        std::cerr << "open fail" << std::endl;
        return 0xdead;
    }
    try
    {
        using namespace turing;
        machine m = load(input);
        return run(m);
    }
    catch (std::runtime_error& e) {
        std::cerr << "Aborted: " << e.what() << std::endl;
    }
    return 0xdead;
}

@Aliksan · 05.10.2016, 17:17 **[ТС]**

Господи, это работает ... Я неделю ломал голову над изменениями в своей программе, а вы в своей буквально сразу переделали под мой случай. Max Dark, большое вам спасибо. Вы очень мне помогли!

@danell · 15.02.2017, 21:49

Aliksan, Hello, i have a similar problem with my Turing machine, if still have it, could you write working code to me. I would really appreciate that.

@Aliksan · 15.02.2017, 21:56 **[ТС]**

The program was written above.

C++

/**
 * @file machine.cpp
 * @compile g++ -std=c++11 -Wall -Wpedantic -Wextra -Werror -O2 -mtune=native machine.cpp -o machine
 * */
 
#include <string>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <map>
 
namespace tools {
    std::string right_trim(const std::string &str) noexcept {
        std::string::size_type last_space = str.find_last_not_of(" \t\r\n");
        return last_space == std::string::npos ? "" : (
                str.size() == (last_space + 1) ? str : str.substr(0, last_space + 1)
        );
    }
}
 
namespace turing {
    /**
     * direction constants
     */
    enum directions {
        RIGHT = 'R',
        LEFT  = 'L',
        SAME  = '*'
    };
    template<typename T1, typename T2>
    using map = std::map<T1, T2>;
    using state_type = std::string;
    using symbol_type = char;
 
    /**
     * next state for turing::machine
     */
    struct next_state {
        /**
         * move direction
         */
        symbol_type direction;
        /**
         * next state
         */
        state_type next_state;
        /**
         * replace symbol
         */
        symbol_type next_char;
    };
 
    using state_list = map<symbol_type, next_state>;
    using state_map = map<state_type, state_list>;
 
    /**
     * machine state
     */
    struct machine {
        /**
         * current head position
         */
        size_t head_position;
        /**
         * current state
         */
        state_type state;
        /**
         * machine "tape"
         */
        std::string tape;
        /**
         * state table
         */
        state_map state_table;
    };
 
    /**
     * load machine state from input stream
     * 
     * @param input stream 
     * @return loaded state
     * @throw std::runtime_error if cant parse state line
     */
    machine load(std::istream& input) throw(std::runtime_error) {
        machine m;
        std::string line;
 
        input >> m.head_position;
        input >> m.tape;
 
        while (std::getline(input, line)) {
            line = tools::right_trim(line);
            if (line.empty())
                continue;
            std::istringstream parser(line);
            state_type current_state, next_state;
            symbol_type current_char, next_char, direction;
 
            parser >> current_state >> current_char >> next_char >> direction >> next_state;
            if (parser.fail()) {
                throw std::runtime_error("parser.fail()");
            }
            // fill state for current state+char pair
            {
                auto& state = m.state_table[current_state][current_char];
                state.direction  = direction;
                state.next_char  = next_char;
                state.next_state = next_state;
            }
        }
        m.state = m.state_table.begin()->first;
        m.tape = tools::right_trim(m.tape);
        --m.head_position;
        return m;
    }
 
    /**
     * run machine
     * @param m machine state
     * @return 0
     * @throw std::runtime_error if cant find next state
     * @throw std::out_of_range if head outside tape
     */
    int run(machine& m) throw(std::runtime_error, std::out_of_range) {
        bool in_cycle = false;
        bool stop = false;
 
        while (!stop) {
            state_map::iterator state;
            state_list::iterator next;
 
            // find state table for current state
            state = m.state_table.find(m.state);
            if (state == m.state_table.end()) {
                // m.state missing in m.state_table
                throw std::runtime_error("state == m.state_table.end()");
            }
            // find next state for current symbol
            const auto current_symbol = m.tape.at(m.head_position);
            next = state->second.find(current_symbol);
            if (next == state->second.end()) {
                // no rule for current_symbol, try find rule for "any" symbol
                next = state->second.find('*');
            }
            if (next == state->second.end()) {
                // current_symbol missing in m.state_table[m.state]
                throw std::runtime_error("next == state->second.end()");
            }
            next_state new_state = next->second;
            // no change if next char == '*'
            if (new_state.next_char != '*') {
                m.tape[m.head_position] = new_state.next_char;
            }
            m.state = new_state.next_state;
 
            switch (new_state.direction) {
                case RIGHT:
                    in_cycle = false;
                    m.head_position++;
                    break;
                case LEFT:
                    in_cycle = false;
                    m.head_position--;
                    break;
                case SAME:
                    if (in_cycle) {
                        throw std::runtime_error("loop detected");
                    }
                    in_cycle = true;
                    break;
                default:
                    throw std::runtime_error("wrong direction");
            }
            std::cout << m.tape << std::endl;
            stop = m.state == "X";
        }
        return 0;
    }
}
 
int main(int argc, char** argv) {
    std::string file_name;
    std::ifstream input;
 
 
    if (argc == 1) {
        std::cout << "Enter file name > ";
        std::cin >> file_name;
    } else {
        file_name = argv[1];
    }
 
    input.open(file_name);
 
    if (!input.is_open()) {
        std::cerr << "open fail" << std::endl;
        return 0xdead;
    }
    try
    {
        using namespace turing;
        machine m = load(input);
        return run(m);
    }
    catch (std::runtime_error& e) {
        std::cerr << "Aborted: " << e.what() << std::endl;
    }
    return 0xdead;
}

@Aliksan 7 / 7 / 3 Регистрация: 22.09.2015 Сообщений: 173
	05.10.2016, 15:56 [ТС]	5
	Очень сложно у вас написано, сразу чувствуется, что код писал не любитель программирования и даже не студент... Буду смотреть ваш код. 1.тхт тестировался тут. И результат без знаков умножения и букв A, B, C. Добавлено через 6 минут Один студент сказал, что проблему решил после того, как отсортировал инструкции. Я взял и сортировку сделал не в коде а в 1.тхт, естественно, проблему это не решило. Добавлено через 19 минут Только что проверил ваш код на работоспособность, та же история ... 1.тхт тупит. Пытался подрихтовать сам 1.тхт, удалить пару тройку инструкций, кой-что изменить, но в итоге это еще сложнее, чем подправить код. 0

@Aliksan 7 / 7 / 3 Регистрация: 22.09.2015 Сообщений: 173
	05.10.2016, 17:17 [ТС]	7
	Господи, это работает ... Я неделю ломал голову над изменениями в своей программе, а вы в своей буквально сразу переделали под мой случай. Max Dark, большое вам спасибо. Вы очень мне помогли! 0

@danell 0 / 0 / 0 Регистрация: 15.02.2017 Сообщений: 1
	15.02.2017, 21:49	8
	Aliksan, Hello, i have a similar problem with my Turing machine, if still have it, could you write working code to me. I would really appreciate that. 0

Машина Тьюринга: не хватает одного IF в программе

Решение