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

我究竟做错了什么。在另一个问题中，回答说模拟非确定性有限自动机转换的最佳方法是使用映射，但使用映射适合此类问题还是可以以任何方式解决？为什么这些值会丢失？

更改地图结构是否方便？IE：

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

3 回答 3

2

映射是1-to-1键和值之间的关系，因此它可以表示确定性自动机。

非确定性自动机可以由1-to-many关联容器表示。

即您需要 astd::multimap或者您可以继续使用std::map带有值类型的 a 不同容器：

 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) 因此地图忽略了一个。

您可以通过将地图制作为：（更改 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 回答