は、C++、私は言葉が決定性有限オートマトン</p> <p>Iのための遷移関数によって受け入れられているかどうかを決定する必要がありオートマトン理論の割り当てを、やっている

Question

の中に非決定性有限オートマトンをシミュレートするためのコードを実装します次いで、入力は4つの整数で始まり、最初のオートマトンのための状態の数であり、次の、3番目の数字は、初期状態オートマトンの遷移の数であり、そして

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 

：この入力ファイルを持っています最終状態の数最後の状態になります（この例では、最終状態は2と5です）。

次にN行（Nは遷移の数）で、それぞれ2つの整数と文字I、J、Cがあり、遷移、つまり遷移が状態iから状態Jに移行する状態を表します。この行に続いて、テストする文字列の数を含む単一の整数Sと、それぞれの文字列のS行が含まれます。

このプログラムの出力は次のようになります。文字列が受理または拒否された場合

Case #2: 
aaabcccc Rejected 
aabbbbcdc Rejected 
acdddddd Accepted 

それは言う必要があります。これまでのところ、私は入力を使って作業をコード化しました。

私はどのようにオートマトンを表すのが最も便利だろうか分かりません。私は単に配列を使うべきですか？配列にどのようなロジックを適用しますか？オートマトンアルファベットを事前に知らなくてもそれを行う方法はありますか？私はオートマトンを表現するためにデータ構造が必要ですか？私はこの課題に少しついていますし、いくつかのアイデア、いくつかの擬似コード、またはアイデアが好きです。コードは別の言語ですか？ 、私は私の割り当てをしたいので、私は、解決策を望んでいないが、私はいくつかの助け

Answer 1

を使用することができれば、私はあなたがi状態状態jへの移行がc経由がある場合tr[(i, c)] = j遷移のためのマップtrを持つことができると思います最終状態の配列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 
};