在c ++中设计非确定性有限自动机（不正确的输出） [英] Design a nondeterministic finite automata in c++ (incorrect output)

问题描述

我正在做一个模拟非确定性有限自动机的赋值，正如我在 tarea4.in 中读取：

I am doing an assignment for simulate a nondeterministic finite automaton, just as I explain in this post. I have this input read from the file 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是一个最终状态。

The first line of input is an integer T, represented the number of cases to evaluate the program. Each test case starts with 4 integers, the first is the number of state for the automaton, next is the number of transitions of the automaton, the third number is the initial state, and then the number of final states. then come the final states (in the example the final states are 2 and 5). Then come F lines, each with an integer E, representing E is a final state.

然后是N行（N是转换数），每个具有2个整数和字符I，J和C，表示转换，转换从状态i转到状态J，其中字符为C.跟在这一行后面有一个整数S，它将包含要测试的字符串数量，然后S行与相应的字符串。

Then come N lines (N is the number of transitions), each with 2 integers and a character, I, J and C, representing the states where the transition, ie, the transition goes from state i to state J with the character C. Following this line come with a single integer S, which will contain the number of strings to test, then S lines with the respective strings.

预期输出为：

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 ，以某种方式检查可以采取自动机评估字符串的非确定性的不同路径？

My question is: Why do I get incorrect output? I think it is for the nondeterminism of the automaton defined in the test case, but how I can evaluate the string correctly?. How I can change my function called evaluate_string to that in some way check the different paths that can take the automaton to evaluate the string by the non-determinism?

我已经坚持这个几天了，说实话我有点绝望。

I've been stuck with this for several days and to be honest I am somewhat desperate about.

推荐答案

评估NFA与评估DFA几乎一样简单 >

在DFA中，您有一个当前状态，并且在每个步骤中选择下一个转换。在输入结束时，您检查当前状态是否为接受状态。

In a DFA, you have one current state and in each step you select the next transition. At the end of the input, you check whether the current state is an accepting state.

好吧，在NFA中，您有一个当前状态，并且在每个步骤中，您将浏览所有当前状态，并为每个状态选择所有有效的转换。

Well, in an NFA you have a set of current states, and in each step you go through all current states, and for each, you select all valid transitions. Those combined sets form your new state set.

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

At the end, you check whether the intersection of the current states and the accepting states is non-empty.

在伪代码中，它如下所示：

In Pseudo-code this looks as follows:

• = ： 每个 > 每次 i 转换 转换 转换 i> [ ] [ ]：
  
  
  
  • （ target_of （ transition ））
  
  
  • current = { initial }
  • for each char in input:
    • next = { }
    • for each state in current:
      • for each transition in transitions[state][char] ∪ transitions[state][ϵ]:
        • next.append(target_of(transition))
        
        
        • 打印 接受字符串
        
        
        • print "String accepted"
        
        
        • print
        
        
        • print "String rejected"

        逐行，转换为C ++代码。为了方便起见，我建议对当前和使用 std :: set< int> > next 集，以及一个 std :: multimap 的向量。这假设每个状态对应一个整数。

        This can be translated, line by line, into C++ code. To make this easy, I suggest using std::set<int> for the current and next sets, and a vector of std::multimap<char, int> for the transitions. This assumes that each state corresponds to an integer.

        这篇关于在c ++中设计非确定性有限自动机（不正确的输出）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！