Entwerfen Sie einen nichtdeterministischen endlichen Automaten in C++ (falsche Ausgabe)

Question

Ich mache eine Zuweisung für die Simulation eines nichtdeterministischen endlichen Automaten, so wie ich es in dieser post erkläre. Ich habe diese Eingabe aus der Datei gelesen 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 

Die erste Zeile der Eingabe eine ganze Zahl T, die Anzahl der Fälle dargestellt, das Programm zu bewerten. Jeder Testfall beginnt mit 4 ganzen Zahlen, die erste ist die Anzahl der Zustände für den Automaten, die nächste ist die Anzahl der Übergänge des Automaten, die dritte Zahl ist der Anfangszustand und dann die Anzahl der Endzustände. dann kommen die Endzustände (im Beispiel sind die Endzustände 2 und 5). Dann kommen F-Linien mit jeweils einer ganzen Zahl E, die E als Endzustand darstellt.

Dann kommen N Zeilen (N ist die Anzahl der Übergänge), jeweils mit 2 ganzen Zahlen und einem Zeichen, I, J und C, die die Zustände darstellen, wo der Übergang, dh der Übergang vom Zustand i zum Zustand J mit geht das Zeichen C. Nach dieser Zeile kommt eine einzelne ganze Zahl S, die die Anzahl der zu testenden Strings enthält, dann S Zeilen mit den entsprechenden Strings.

die erwartete Ausgabe ist:

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

Der Ausgang in meinem Code resultierende:

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

Hier ist mein Code:

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

Meine Frage ist: Warum bekomme ich falsch Ausgabe? Ich denke es ist für den Nichtdeterminismus des im Testfall definierten Automaten, aber wie kann ich den String richtig auswerten? Wie kann ich meine Funktion mit der Bezeichnung evaluate_string ändern, um in gewisser Weise die verschiedenen Pfade zu überprüfen, die den Automaten dazu bringen können, die Zeichenfolge durch den Nicht-Determinismus zu bewerten?

Ich bin seit einigen Tagen mit diesem fest und um ehrlich zu sein bin ich etwas verzweifelt.

Answer 1

Die Auswertung eines NFA ist fast so einfach als Bewertung eines DFA.

In einem DFA haben Sie einen aktuellen Status und in jedem Schritt wählen Sie den nächsten Übergang aus. Am Ende der Eingabe prüfen Sie, ob der aktuelle Zustand ein akzeptierender Zustand ist.

Nun, in einem NFA haben Sie einen Satz der aktuellen Zustände, und in jedem Schritt durchlaufen Sie alle aktuellen Zustände, und für jeden, wählen Sie alle gültigen Übergänge. Diese kombinierten Sets bilden Ihren neuen Staatssatz.

Am Ende überprüfen Sie, ob der Schnittpunkt der aktuellen Zustände und der akzeptierenden Zustände nicht leer ist.

In Pseudo-Code sieht das wie folgt aus:

• aktuelle = { anfänglichen}
• für jeden charin Eingang:
  • nächste {=}
  • für jeden Zustandin aktuellen:
    • für jeden Übergangin Transitionen [ Zustand] [ char] ∪ Transitionen [ Zustand] [ ε]:
      • nächsten. append ( target_of ( Übergang))
  • aktuellen = nächsten
• wenn len ( Schnitt ( aktuellen, Annahme))> 0:
  • Druck"String accepted"
• sonst:
  • Druck"String rejected"

Diese kann übersetzt werden, Zeile für Zeile, in C++ - Code.Um dies zu vereinfachen, empfehle ich die Verwendung von std::set<int> für die current und next Sätze und einen Vektor von für die Übergänge. Dies setzt voraus, dass jeder Zustand einer ganzen Zahl entspricht.

Answer 2

Ich denke, Sie sollten zuerst den allgemeinen Mechanismus implementieren, um alle NFA in die entsprechende DFA zu konvertieren. Nachdem Sie dies getan haben, können Sie den Automatenläufer einfach implementieren, da DFAs deterministisch arbeiten.

Answer 3

Das grundlegende Problem ist, dass Ihr Code aus der Übergangsschleife ausbricht, sobald Sie den ersten gültigen Übergang finden. Das würde funktionieren, wenn Sie ein DFA ausführen würden, aber ein NFA könnte mehrere gültige Pfade haben.

Zwei Möglichkeiten Sie haben (ich bin sicher, dass es mehr gibt):

1) Evaluator einen NFA implementieren: Es handelt sich aus einer Reihe von aktuellen Zuständen und Auswertung jedes Eingabezeichen gegen jeden Staat zu verfolgen. Sobald der String gelesen wurde, ist er abgeschlossen, wenn einer der Endzustände in der Menge enthalten ist.

2) Wandeln Sie das NFA in ein DFA um, was meiner Ansicht nach der härtere Ansatz ist, da das im Grunde die gleiche Satzlogik erzeugt und die Übergänge für die neuen Zustände bewertet.