Frage an nfa, c++, automaton – Entwerfen Sie eine nicht deterministische endliche Automaten in C ++ (falsche Ausgabe)

6

Ich mache eine Aufgabe, um einen nichtdeterministischen endlichen Automaten zu simulieren, so wie ich es hier erklärePost. Ich habe diese Eingabe aus der Datei gelesentarea4.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 Eingabezeile ist eine Ganzzahl T, die die Anzahl der Fälle angibt, in denen das Programm ausgewertet werden soll. 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 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 Zeilen mit jeweils einer ganzen Zahl E, die E als Endzustand darstellen.

Dann kommen N Zeilen (N ist die Anzahl der Übergänge) mit jeweils 2 ganzen Zahlen und einem Zeichen I, J und C, die die Zustände darstellen, in denen der Übergang, dh der Übergang von Zustand i zu Zustand J mit dem Zeichen C erfolgt. Nach dieser Zeile folgt eine einzelne Ganzzahl S, die die Anzahl der zu testenden Zeichenfolgen enthält, und dann S mit den entsprechenden Zeichenfolgen.

Die erwartete Ausgabe ist:

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

Die Ausgabe, die zu meinem Code führt:

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 erhalte ich eine falsche Ausgabe? Ich denke es ist für den Nichtdeterminismus des Automaten im Testfall definiert, aber wie kann ich den String richtig auswerten ?. Wie kann ich meine aufgerufene Funktion ändern?evaluate_string um das irgendwie zu überprüfen, die verschiedenen Pfade, die der Automat nehmen kann, um die Zeichenfolge durch den Nicht-Determinismus zu bewerten?

Ich bin schon seit einigen Tagen damit festgefahren und ehrlich gesagt bin ich etwas verzweifelt.

Bitte formatieren Sie Ihren Code beim nächsten Mal richtig. Ihre Einrückungen waren weit weg. Außerdem verstehe ich die erwartete Ausgabe nicht. Zum Beispiel, wo ist0 b 3 kommen von? Was willst du zum Schluss? Ein NFA oder ein DFA? Nichts in Ihrem Beitrag ist ein deterministischer Automat (weder die Eingabe noch die erwartete Ausgabe), daher habe ich Erwähnungen von "DFA" vorerst entfernt. Konrad Rudolph
Das ist nicht das was ich meine. Das0 b 3 Ist von der Übergangsfunktion keine Eingabe zu berücksichtigen. - Zu Ihrer Frage: Ah, verstanden. Die schlechte Nachricht ist: Sie können eine NFA in eine DFA umwandeln und lösen, aber Sie können nicht die identische Ausgabe des Statusübergangs erhalten, weil Ihre Statusnamenwerden sich unterscheiden. Außerdem ist es wahrscheinlich einfacher, den NFA direkt auszuführen (nicht einmal 10 Zeilen!), Als ihn zuerst in einen DFA umzuwandeln. Konrad Rudolph
@KonradRudolph Die Zustandsübergänge spielen keine Rolle, ich drucke sie nur aus, um zu sehen, was bei jedem Zustandswechsel passiert. Das Programm muss lediglich anzeigen, ob der String akzeptiert oder abgelehnt wird.running the NFA directly is probably easier (not even 10 lines!): die frage ist: wie kann ich das machen? Wie soll ich meinen Code ändern, um dies zu tun? novaKid
where is 0 b 3 coming from?: für die Eingabe aabbbbcdc sind die Übergänge des Automaten:(q0, a) = 0, (q0, a) = 0, (q0, b) = 3, (q3, b) = 0, (q0, b) = 3, (q3, b) = 0   'welches willst du?'; Meine Funktion "evaluation_string" implementiert einen DFA und ich möchte wissen, wie ich ihn ändern kann, um einen NFA zu erhalten novaKid

Deine Antwort

3   die antwort
9

Bewertung einer NFA istfast so einfach als Bewertung eines DFA.

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

Nun, in einer NFA haben Sie eineeinstellen der aktuellen Zustände, und in jedem Schritt durchlaufen Sie alle aktuellen Zustände und wählen für jeden alle gültigen Übergänge aus. Diese kombinierten Mengen bilden Ihre neue Zustandsmenge.

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

Im Pseudocode sieht das so aus:

aktuell = {Initiale }für jeden verkohlen im Eingang:Nächster = {}für jeden Zustand im aktuell:für jeden Übergang im Übergänge[Zustand] [verkohlen] ∪Übergänge[Zustand] [ϵ]:Nächster.anhängen(target_of(Übergang))aktuell = Nächsterob len(Überschneidung(aktuell, annehmen))> 0:drucken "String accepted"sonst:drucken "String rejected"

Dies kann übersetzt werden,Zeile für Zeilein C ++ - Code. Um dies zu vereinfachen, empfehle ich die Verwendung vonstd::set<int> für diecurrent undnext Sätze und ein Vektor vonstd::multimap<char, int> für die Übergänge. Dies setzt voraus, dass jeder Zustand einer ganzen Zahl entspricht.

@KonradRudolph Ihr Algorithmus deckt nicht abƐ-Bewegungen ajmartin
@ajmartin Verdammt, ich hatte nicht gedacht, dass ϵ Bewegungen transitiv sind. Vielen Dank, dass Sie sich die Zeit genommen haben, diese Antwort zu überprüfen. Leider habe ich jetzt keine Zeit, dies zu korrigieren, aber ich werde es in naher Zukunft tun. Konrad Rudolph
@ajmartin Ups. Besser jetzt? Off the top of my head ϵ Bewegungen brauchen keine besondere Behandlung (abgesehen davon, dass sie überhaupt in Betracht gezogen werden), oder? Konrad Rudolph
@KonradRudolphfor each transition in transitions[state][char]: next.append(target_of(transition))Ich verstehe diese Zeilen nicht, Einrückung ist schlecht odernext.append(target_of(transition)) sollte in der Schleife sein? novaKid
1

Ich denke, Sie sollten zuerst den allgemeinen Mechanismus implementieren, um einen NFA in den entsprechenden DFA umzuwandeln. Danach können Sie mühelos Automaten-Runner implementieren, da DFAs deterministisch arbeiten.

1

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

Sie haben zwei Möglichkeiten (ich bin sicher, es gibt noch mehr):

1) Implementieren Sie einen NFA-Evaluator: Hierzu müssen Sie eine Reihe aktueller Zustände verfolgen und jedes Eingabezeichen anhand jedes Zustands bewerten. Sobald die Zeichenfolge gelesen wurde, ist sie vollständig, wenn sich einer der Endzustände in der Menge befindet.

2) Konvertieren Sie den NFA in einen DFA, was meiner Meinung nach der schwierigere Ansatz ist, da dies im Wesentlichen das Erstellen derselben Mengenlogik und das Auswerten der Übergänge für die neuen Zustände umfasst.

Wie kann ich meinen Code ändern, um das zu tun, was Sie in Ihrer Option angeben? 1)Implement an NFA evaluator. Gibt es etwas Pseudocode zu tun? Ich habe viele Zweifel an der Logik des NFA-Evaluators. novaKid
Hey Mann, müssen Sie Rekursion verwenden, um die NFA zu machen ?. Ich kann den Weg nicht finden, irgendwelche Vorschläge außer dem, was Sie mir angedeutet haben? novaKid
@novaKid Konrads Beitrag lesen. Dave S

Verwandte Fragen