특정 입력에 내 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

Heres는 C++로 내 구현 :

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 

나는이 입력이

#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; 
} 

그러나 내 코드 출력으로 생성합니다 :

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 

미묘한하지만 걸림이 발생할 수 있습니다 위에 루핑 확실히 원하는 결과를 제공하지 않습니다 동안 현재의 재 할당.