Реализация кода для симуляции недетерминированного конечного автомата в C++

Question

Я делаю задание для теории автоматов, которое я должен определить, принимается ли слово функцией перехода для детерминированного конечного автомата

У меня есть этот входной файл:

6 8 0 2
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
3
aaabcccc
aabbbbcdc
acdddddd

Входные данные начинаются с 4 целых чисел, первое - номер состояния автомата, затем число переходов автомата, третье число - начальное состояние, а затем число конечных состояний. затем идут конечные состояния (в примере конечные состояния 2 и 5).

Затем идут N строк (N - количество переходов), каждое из которых содержит 2 целых числа и символ I, J и C, представляющих состояния, в которых происходит переход, т. Е. Переход из состояния i в состояние J с символом C. После этой строки идет одно целое число S, которое будет содержать количество проверяемых строк, затем S строк с соответствующими строками.

Вывод этой программы должен быть:

Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
acdddddd Accepted

Должно быть указано, принята строка или отклонена. So far, I've only coded the work with the input.

I don't know how would be most convenient to represent the automaton. Should I simply use arrays? What logic would I apply to the arrays?. Is there any way to do it without knowing in advance the automaton alphabet? Do I need a data structure to represent automata?. I am a little stuck with this assignment, and would like some ideas, some pseudocode or ideas to do it. Is the code in another language? I do not want the solution, because I want to do my assignment but if I could use some help

Answer 1

Я думаю, что вы можете иметь картуtr для переходов где tr[(i, c)] = j если есть переход от i государство для j состояние через c, массив для конечных состояний fs[m] где m число конечных состояний и целое число для начального состояния s0,

Сильфон - это рамка класса с такими свойствами:

class Automata
{
public:
    Automata(int start) : s0(start)
    {}

    void add_transition(int i, int j, char c) {
        //...
    }

    void add_final_state(int i) {
        //...
    }

    bool validate_string(const std::string& str) {
        //...
    }
private:
    std::map<std::pair<int, char>, int> tr; // transitions
    std::vector<int> fs; // final states
    int s0; // initial state
};