0

この投稿に示されているように、状態遷移を格納しているマップを使用して、非決定性有限オートマトンをシミュレートするために数日間試みています。

問題は、非決定論的な遷移、つまり同じシンボルによって私を異なる状態に導く遷移が欠落していることです。これが私のコードです：

#include <iostream>
#include <map>
#include <utility>
#include <iterator> // for ostream_iterator

using namespace std;

int main (){

    freopen ("testMap.in", "r", stdin);
    int testCases;
    int i, j;

    int stateOrigin, stateDestination;
    char transitionCharacter ;
    int numberTransitions=8;

        typedef map<pair<int, char>, int> transitions;
        transitions trans;

          for (j=0; j<numberTransitions;j++){
             cin>> stateOrigin>>stateDestination>>transitionCharacter;
             trans.insert(transitions::value_type(std::make_pair(stateOrigin,transitionCharacter), stateDestination ));
        }

        map<pair<int, char>, int>::iterator p = trans.begin();

       for( p = trans.begin(); p != trans.end(); p++ ){
         cout << p->first.first<< " "<<p->first.second<<" "<<p->second<<endl;
       }

return 0;
}

マップの内容全体を印刷すると、次のようになります。

0 a 0
1 b 1
1 c 2
3 d 4
4 d 4

期待される出力は次のとおりです。

0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d

私は何を間違っているのですか。別の質問では、非決定性有限オートマトンの遷移をシミュレートする最良の方法はマップを使用することですが、マップを使用することはこのタイプの問題に適切であるか、または何らかの方法で解決できると答えました。なぜこれらの値が失われるのですか？

マップ構造を変更すると便利ですか？すなわち：

typedef map<pair<int, int>, char> transitions;
4

3 に答える 3

2

マップは1-to-1キーと値の間の関係であるため、決定性オートマトンを表すことができます。

非決定性オートマトンは、1-to-many連想コンテナで表すことができます。

つまり、が必要であるstd::multimapかstd::map、値型が異なるコンテナでを使用し続けることができます。

 typedef map<pair<int, int>, vector<char> > transitions;

したがって、ペアcharごとに複数の値を持つことができます。int

于 2012-05-16T06:28:06.697 に答える
1

あなたはtypedefを使うことができます、それは合法です。

std :: mapでは、キーは一意である必要があるため、同じペア値があると思います。このような場合は、std :: multimapを使用してみてください。これは、複数のキー値を格納できるためです。

編集：わかりました、問題は次のとおりです：

map<pair<int, char>, int>::iterator p = trans.begin();

あなたはペアを持っています。あなたは見ることを期待します：

0 0 a
0 1 a

ただし、キーは（0、a）と（0、a）であるため、マップは1つを無視します。

マップを次のように作成することで、これを回避できます:(intとcharの順序を変更する）

typedef map<pair<int, int>, char> transitions;
于 2012-05-16T06:30:04.477 に答える
0

マップはペアであるため、インサートは常にペアを探します<>、マップの最初の要素はペアであるため、このコードを試してください

 trans.insert(std::make_pair(std::make_pair(stateOrigin,transitionCharacter), stateDestination ));
于 2012-05-16T06:34:26.283 に答える