实现一个代码来模拟有限自动机用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如果通过c从i状态j状态转换，用于最终状态的阵列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 
};