सी ++ (गलत आउटपुट)

Question

में एक नोडेटर्मिनिस्टिक परिमित ऑटोमाटा डिज़ाइन करें, मैं इस post में समझाता हूं, जैसा कि मैं एक nondeterministic परिमित automaton अनुकरण करने के लिए एक असाइनमेंट कर रहा हूं।

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 

इनपुट की पहली पंक्ति एक पूर्णांक टी, कार्यक्रम का मूल्यांकन करने के मामलों की संख्या का प्रतिनिधित्व किया है: मैं इस इनपुट फ़ाइल tarea4.in से पढ़ा है। प्रत्येक परीक्षण केस 4 पूर्णांक के साथ शुरू होता है, पहला automaton के लिए राज्य की संख्या है, अगला automaton की संक्रमण की संख्या है, तीसरा नंबर प्रारंभिक स्थिति है, और फिर अंतिम राज्यों की संख्या है। फिर अंतिम राज्य आते हैं (उदाहरण में अंतिम राज्य 2 और 5 हैं)। फिर एफ लाइनें, प्रत्येक एक पूर्णांक ई के साथ, ई का प्रतिनिधित्व एक अंतिम राज्य है।

फिर एन लाइनें (एन संक्रमण की संख्या है), प्रत्येक 2 पूर्णांक और एक चरित्र, आई, जे और सी के साथ, उन राज्यों का प्रतिनिधित्व करते हैं जहां संक्रमण, यानी, संक्रमण राज्य से जाता है, मैं जे को राज्य करता हूं चरित्र सी। इस पंक्ति के बाद एक पूर्णांक एस के साथ आते हैं, जिसमें परीक्षण करने के लिए स्ट्रिंग की संख्या होगी, फिर संबंधित तारों के साथ एस लाइनें होंगी।

उम्मीद उत्पादन होता है:

Test Case #2: 
aaabcccc Rejected 
aabbbbcdc Rejected 
abbcdddcc Rejected 
acdddddd Accepted 
abc Accepted 

उत्पादन मेरी कोड में जिसके परिणामस्वरूप:

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

मेरा प्रश्न है:: क्यों मैं गलत मिलता है

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

यहाँ मेरी कोड है उत्पादन? मुझे लगता है कि यह टेस्ट केस में परिभाषित automaton के nondeterminism के लिए है, लेकिन मैं स्ट्रिंग का सही ढंग से मूल्यांकन कैसे कर सकता हूं? मैं evaluate_string नामक अपने फ़ंक्शन को कैसे बदल सकता हूं, किसी भी तरह से अलग-अलग पथों की जांच करें जो स्ट्रिंग का मूल्यांकन गैर-निर्धारणा द्वारा स्ट्रिंग का मूल्यांकन करने के लिए कर सकते हैं?

मैं कई दिनों से इसके साथ अटक गया हूं और ईमानदार होने के लिए मैं कुछ हद तक हताश हूं।

Answer 1

एनएफए का मूल्यांकन लगभग डीएफए का मूल्यांकन करने के रूप में लगभग के रूप में आसान है।

एक डीएफए में, आपके पास एक वर्तमान स्थिति है और प्रत्येक चरण में आप अगले संक्रमण का चयन करते हैं। इनपुट के अंत में, आप जांचते हैं कि वर्तमान स्थिति एक स्वीकार्य स्थिति है या नहीं।

ठीक है, एनएफए में आपके पास वर्तमान राज्यों के सेट हैं, और प्रत्येक चरण में आप सभी मौजूदा राज्यों के माध्यम से जाते हैं, और प्रत्येक के लिए, आप सभी मान्य संक्रमणों का चयन करते हैं। वे संयुक्त सेट आपके नए राज्य सेट बनाते हैं।

अंत में, आप जांचते हैं कि वर्तमान राज्यों और स्वीकार्य राज्यों का चौराहे खाली नहीं है या नहीं।

छद्म कोड में यह इस प्रकार है:

• वर्तमान = { प्रारंभिक}
• प्रत्येक चार के लिए इनपुट में:
  • अगले = {} वर्तमान
  • प्रत्येक राज्य के लिए में:
    • प्रत्येक संक्रमण के लिए में संक्रमण [ राज्य] [ चार] ∪ बदलाव [ राज्य] [ ε]:
      • अगला। संलग्न ( target_of ( संक्रमण))
  • वर्तमान = अगले
• अगर लेन ( चौराहे ( वर्तमान, स्वीकार करने))> 0:
  • प्रिंट"String accepted"
• बाकी:
  • प्रिंट"String rejected"

यह अनुवाद किया जा सकता है, लाइन द्वारा लाइन, सी ++ कोड में।इसे आसान बनाने के लिए, मैं std::set<int>current और next सेट के लिए, और संक्रमण के लिए std::multimap<char, int> के वेक्टर का उपयोग करने का सुझाव देता हूं। यह मानता है कि प्रत्येक राज्य एक पूर्णांक से मेल खाता है।

Answer 2

मुझे लगता है कि आपको किसी भी एनएफए को इसके संबंधित डीएफए में बदलने के लिए पहले सामान्य तंत्र को लागू करना चाहिए। ऐसा करने के बाद, आप डीएफए कार्य निर्धारित रूप से काम करने के बाद से स्वचालित रूप से automaton धावक को कार्यान्वित कर सकते हैं।

Answer 3

मौलिक समस्या यह है कि जैसे ही आपको पहला मान्य संक्रमण मिल जाता है, आपका कोड संक्रमण लूप से बाहर हो रहा है। यदि आप डीएफए कर रहे थे तो कौन सा काम करेगा, लेकिन एनएफए में कई वैध पथ हो सकते हैं।

दो विकल्प आपके पास (मुझे यकीन है कि वहाँ और अधिक कर रहे हैं हूँ):

1) एक NFA मूल्यांकनकर्ता को लागू करें: यह वर्तमान राज्यों का एक सेट का ट्रैक रखने, और प्रत्येक राज्य के खिलाफ प्रत्येक इनपुट चरित्र का मूल्यांकन शामिल है। एक बार स्ट्रिंग पढ़ी जाने के बाद, यदि अंतिम राज्यों में से कोई भी सेट में है, तो यह पूरा हो गया है।

2) एनएफए को एक डीएफए में परिवर्तित करें, जो कि आईएमएचओ कठिन दृष्टिकोण है, क्योंकि मूल रूप से उसी सेट तर्क का निर्माण और नए राज्यों के लिए संक्रमण का मूल्यांकन करना शामिल है।