实现一个代码来模拟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

它应该说是否接受或拒绝字符串.到目前为止,我只使用输入编写了工作.

我不知道如何最方便地表示自动机.我应该只使用数组吗？我将什么逻辑应用于数组？有没有办法在不事先知道自动机字母表的情况下做到这一点？我需要一个数据结构来表示自动机吗？我对这项任务感到有点困惑,并希望有一些想法,一些伪代码或想法.代码是用另一种语言编写的吗？我不想要解决方案,因为我想做我的任务但是如果我可以使用一些帮助

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
};