在c ++中设计一个非确定性有限自动机(输出不正确)

Question

我正在做一个模拟非确定性有限自动机的任务,正如我在这篇文章中解释的那样.我从文件中读取了这个输入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转到状态J,字符为C.在这一行之后加上一个整数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中你有一组当前状态,并且在每一步中你都会经历所有当前状态,并且对于每一个状态,你选择所有有效的转换.这些组合集构成了您的新状态集.

最后,检查当前状态和接受状态的交集是否为非空.

在伪代码中,这看起来如下:

• current = { initial }
• 为每个 字符 在 输入:
  • 下一个 = {}
  • 对于每个 状态 中 电流:
    • 每个 过渡 在 过渡 [ 状态 ] [ 炭 ]∪ 跃迁 [ 状态 ] [ ε ]:
      • 接下来.追加(target_of(过渡))
  • current = next
• 如果 len(交集(当前,接受))> 0:
  • 打印 "String accepted"
• 否则:
  • 打印 "String rejected"

这可以逐行转换为C++代码.为了简单起见,我建议使用std::set<int>了current与next集和的向量std::multimap<char, int>的转变.这假设每个状态对应一个整数.