设计在C + +（不正确的输出）的非确定性有限自动机(Design a nondeterminist

我做的模拟分配的非确定性有限自动机，就如同我在这个解释后。我有这个输入从文件中读取tarea4.in ：

1
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
5
aaabcccc
aabbbbcdc
abbcdddcc
acdddddd
abc

输入的第一行是一个整数T，表示病例数来评价程序。每个测试用例与4个整数开始，首先是状态自动机的数目，其次是自动机的转换的数量，所述第三数量是初始状态，然后最终状态的数量。然后来最终状态（在本例中的最终状态是2和5）。然后来˚F线，每一个整数E，表示E是最终状态。

然后来N行（N是转变的数量），每个2点的整数和字符，I，J和C，表示其中过渡，即，从状态变为状态i到与字符C.状态j以下这条线来与一个整数S，其中将包含字符串进行测试，则S线与各个串的数目。

预期输出是：

Test Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted

导致我的代码的输出：

Test Case #1:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Rejected
abc Rejected

这里是我的代码：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <vector>    
using namespace std;

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

    int  numberFinals;
    vector<int> currentStates;    

int main (){ 

    freopen ("tarea4.in", "r", stdin);
    //freopen ("tarea4.out", "w", stdout);        
    int testCases, i, j,k, cont=1,finalStates,numberInputs,stateOrigin, stateDestination;
    int numberStates, numberTransitions, initialState;
    char transitionCharacter ;

    set<int> current;
    set<int> next;
    set<int>::iterator it;
    set <int> final;
    std::set<int> the_intersection;  // Destination of intersect
    map<pair<int, int>, char>::iterator p;
    string inputString;

    cin>> testCases;
    for (i=0;i< testCases;i++){
        cin>>numberStates>>numberTransitions>>initialState>>numberFinals;
        current.insert (initialState);

        for (j=0;j<numberFinals;j++){
            cin>>finalStates;
            final.insert(finalStates);
        }

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

        cin>>numberInputs;

        cout<<"Test Case #"<<cont++<<":"<<endl;    

        for (j=0; j<numberInputs;j++){
             //////////////////the code of the answer /////////////////
            current.insert (initialState);
            cin>> inputString;
            cout<<inputString<<" ";


     for (k=0; k<str.size();k++){
         next.clear();
         for ( it=current.begin() ; it != current.end(); it++ ){
              for (q= trans.begin(); q!= trans.end();q++){
                  if((*it == q->first.first)&&(str[k]==q->second)){
                     next.insert(q->first.second);
                   }
              current=next;
              }
         }
     }

            std::set_intersection(current.begin(), current.end(), final.begin(), final.end(), std::inserter(the_intersection, the_intersection.end()));

            if (the_intersection.size()>0){
                cout<< "Accepted"<<endl;
            }
            else{
                cout<< "Rejected"<<endl;
            }

        }

        printf ("\n");
    }

return 0;
}

我的问题是：为什么会得到不正确的输出？我认为这是在测试例定义的自动机的确定性，但如何正确评价串？我怎样才能改变我的函数调用evaluate_string到以某种方式检查，可以采取将自动机评估由非确定性的字符串不同的路径？

我一直坚持这个数天，说实话我对有些绝望。

Answer 1:

评价一个NFA 几乎是评估DFA 一样简单 。

在DFA，你有一个当前状态，并在每个步骤中，您选择一个转变。在输入结束后，你检查当前状态是否处于接受状态。

那么，在NFA你有一组当前状态，并在每个步骤中，您经历的所有当前状态，并为每一个，可以选择所有有效转换。这些组合集合形成新的状态。

最后，你检查的当前状态和接受状态的交集是否非空。

在伪代码，这看起来如下：