在C++中設計一個非確定型有限自動機（不正確的輸出）

Question

我正在做一個模擬非確定型有窮自動機的任務，就像我在這裏解釋的post。我有這個輸入從文件讀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是最終狀態。

然後來N行（N是轉換數），每行有2個整數和一個字符I，J和C，表示轉換的狀態，即轉換從狀態i到狀態J字符C.在這行後面帶有一個整數S，它將包含要測試的字符串的數量，然後用相應的字符串包含S行。

預期的輸出結果是：

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，以某種方式檢查不同的路徑，可以使自動機通過非確定性來評估字符串？

我一直堅持這幾天，說實話我有點絕望。

Answer 1

評估NFA是與評估DFA幾乎一樣容易。

在DFA中，您有一個當前狀態，並在每個步驟中選擇下一個轉換。在輸入結束時，檢查當前狀態是否爲接受狀態。

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

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

在僞代碼這看起來如下：

• 電流 = {初始}
• 每個炭在輸入：
  • 接下來 = {}
  • 每個狀態在電流：
    • 每個過渡在過渡 [狀態] [炭]∪過渡 [狀態] [ε]：
      • 下一個。 追加（ target_of（過渡））
  • 電流 = 下
• 如果 len個（相交（電流，接受））> 0：
  • 打印"String accepted"
• 別的：
  • 打印"String rejected"

這可以將逐行譯成，轉換成C++代碼。爲了方便起見，我建議使用std::set<int>作爲current和next集合，並使用std::multimap<char, int>作爲轉換向量。這假定每個狀態都對應一個整數。

Answer 2

我認爲你應該首先實現一般機制，將任何NFA轉換爲相應的DFA。這樣做後，您可以輕鬆實現自動運行器，因爲DFA確定性地工作。

Answer 3

根本問題是，只要您找到第一個有效的轉換，您的代碼就會突破轉換循環。如果您正在執行DFA，那麼這將起作用，但NFA可能有多個有效路徑。你有

兩個選項（我敢肯定有更多）：

1）實現一個NFA評價：這涉及保持組當前狀態的跟蹤，並評估對每個國家每個輸入字符。一旦字符串被讀取，如果任何最終狀態都在該集合中，則它是完整的。

2）將NFA轉換爲DFA，即IMHO更難的方法，因爲它基本上涉及構建相同的集合邏輯並評估新狀態的轉換。