實現一個代碼來模擬有限自動機用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 
};