爲什麼我的C++程序在特定輸入時崩潰？

Question

有一段時間，我試圖做一個模擬非確定性有窮自動機（NFA）的程序，更具體地說，是一個字符串識別器。經過多次失敗，由於用戶Konrad Rudolph，我可以實現基於這種僞代碼的解決方案：

那麼，在NFA你有一組當前狀態，並在每個步驟中，您經歷的所有的當前狀態，併爲每個選擇所有有效的轉換。這些組合集合形成你的新狀態集。

最後，檢查當前狀態和接受狀態的交集是否非空。

在僞代碼這看起來如下：

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 

對於測試用例的最後一個字符串，程序什麼都不做，只是不停止運行。我的問題是爲什麼我的程序在這個特定的輸入中崩潰。我設計的一樣自動機NFA在JFlap並且識別出這最後的輸入

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 

微妙，但重新分配當前，而循環它可能會導致你的掛起，並絕對不會得到所需的結果。