c++ - 为什么我的 C++ 程序在特定输入时崩溃？

Question

有几天我一直在尝试编写一个程序来模拟非确定性有限自动机 (NFA)，更具体地说，是一个字符串识别器。几经失败，感谢用户Konrad Rudolph ，我可以根据这个伪代码实现一个解决方案:

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.

伪代码如下所示:

current = { initial }
    for each char in input:
        next = { }
        for each state in current:
            for each transition in transitions[state][char]:
                next.append(target_of(transition))
        current = next
if len(intersection(current, accepting)) > 0:
    print "String accepted"
else:
    print "String rejected"

这可以逐行翻译成 C++ 代码。他建议让这变得简单，使用 std::set<int> for the current and next sets

这是我在 C++ 中的实现:

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <utility>
#include <vector>

using namespace std;

int main (){

    int testCases, i, j,k, cont=1,finalStates,numberInputs,stateOrigin, stateDestination;
    int numberStates, numberTransitions, initialState;
    int  numberFinals;
    char transitionCharacter ;

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

    typedef std::pair<int, int> trigger;
    std::map<trigger, char> transitions;
    map<trigger, char>::iterator r;

    cin>> testCases;
    for (i=0;i< testCases;i++){
        
        final.clear();
        next.clear();
        current.clear();
        the_intersection.clear();
        transitions.clear();
        cin>>numberStates>>numberTransitions>>initialState>>numberFinals;

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

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

        cin>>numberInputs;
        current.insert (initialState);
        cout<<"Test Case #"<<cont++<<":"<<endl;
        
        for (j=0; j<numberInputs;j++){
            current.clear();
            current.insert (initialState);
            the_intersection.clear();
            cin>> inputString;
            cout<<inputString<<" ";
            
            /// ///////////////Konrad Rudolph's solution /////////////////
            for (k=0; k<inputString.size();k++){
                next.clear();
                for (it = current.begin(); it!=current.end(); it++){
                    for (r =transitions.begin(); r!=transitions.end(); r++){
                        if ( ((*r).first.first == *it) && ( (*r).second == inputString[k] ) ){
                            next.insert((*r).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.empty()){
                cout<<"Rejected"<<endl;
            }else {
                cout<<"Acepted"<<endl;
            }
            
            /// ///////////////////////////////////////////////////////
        }
        cout<<endl;
    }
return 0;
}

我有这个输入:

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
abc
acdddddd

预期的输出是:

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

但是，我的代码产生的输出是:

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

对于测试用例的最后一个字符串，程序什么都不做，只是不停止运行。我的问题是为什么我的程序会因这个特定输入而崩溃。我在 JFlap 中设计了相同的自动机 NFA并识别最后的输入

acdddddd

.

(0, a) = 1
(1, c) = 2
(2, d) = 3
(3, d) = 4
(4, d) = 4
(4, d) = 4
(4, d) = 4
(4, d) = 5

我在执行代码时遇到了什么错误？

Answer 1

你想做的;

for each char in input:
    next = { }
    for each state in current:
        for each transition in transitions[state][char]:
            next.append(target_of(transition))
    current = next

但是你正在做的是;

for each char in input:
    next = { }
    for each state in current:
        for each transition in transitions[state][char]:
            next.append(target_of(transition))
        current = next

微妙，但在循环时重新分配电流可能会导致挂起，并且肯定不会给出预期的结果。