Pytanie w sprawie automaton, c++, nfa – Zaprojektuj niedeterministyczne automaty skończone w c ++ (niepoprawne dane wyjściowe)

6

Wykonuję zadanie symulowania niedeterministycznego automatu skończonego, tak jak to wyjaśniłem w tymsłupek. Mam to wejście odczytane z plikutarea4.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

Pierwsza linia wejścia to liczba całkowita T, reprezentująca liczbę przypadków do oceny programu. Każdy przypadek testowy zaczyna się od 4 liczb całkowitych, pierwsza to liczba stanów automatu, następnie liczba przejść automatu, trzecia liczba to stan początkowy, a następnie liczba stanów końcowych. potem są ostatnie stany (w przykładzie końcowe stany to 2 i 5). Następnie przychodzą linie F, każda z liczbą całkowitą E, reprezentująca E jest stanem końcowym.

Następnie przychodzą N linii (N jest liczbą przejść), każda z 2 liczbami całkowitymi i znakiem, I, J i C, reprezentującymi stany, w których przejście, tj. Przejście przechodzi ze stanu i do stanu J ze znakiem C. Po tej linii znajduje się jedna liczba całkowita S, która będzie zawierać liczbę ciągów do przetestowania, a następnie linie S z odpowiednimi ciągami.

oczekiwany wynik to:

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

Wynik wynikający z mojego kodu:

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

Oto mój kod:

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

Moje pytanie brzmi: dlaczego otrzymuję nieprawidłowe dane wyjściowe? Myślę, że chodzi o niedeterminizm automatu zdefiniowanego w przypadku testowym, ale jak mogę poprawnie ocenić ciąg ?. Jak mogę zmienić moją funkcję o nazwieevaluate_string w jakiś sposób sprawdzić różne ścieżki, które mogą zająć automat do oceny ciągu przez niedeterminizm?

Utknąłem z tym przez kilka dni i szczerze mówiąc jestem trochę zdesperowany.

@KonradRudolph Przejścia stanów nie mają znaczenia, tylko je drukuję, aby zobaczyć, co dzieje się przy każdej zmianie stanu, program po prostu musi pokazać, czy łańcuch jest akceptowany czy odrzucany.running the NFA directly is probably easier (not even 10 lines!): pytanie brzmi: jak mogę to zrobić ?, utknąłem na tym przez kilka dni. Jak mam zmodyfikować swój kod, aby to zrobić? novaKid
Sformatuj kod poprawnie następnym razem. Twoje wcięcia były daleko. Ponadto nie rozumiem oczekiwanych wyników. Na przykład, gdzie jest0 b 3 pochodzi z? Wreszcie, czego chcesz? NFA lub DFA? Nic w twoim poście nie jest automatem deterministycznym (ani wejściem, ani oczekiwanym wyjściem), więc usunąłem na razie wzmianki o „DFA”… Konrad Rudolph
Nie o to mi chodzi. The0 b 3 pochodzi z funkcji przejścia, nie ma danych do rozważenia. - Jeśli chodzi o twoje pytanie: ah, zrozum. Zła wiadomość to: możesz przekształcić NFA w DFA i rozwiązać go, ale nie możesz uzyskać identycznego wyjścia stanu z tego, ponieważ twoje nazwy stanówbędzie różnić się. Również uruchomienie NFA bezpośrednio jest prawdopodobnie łatwiejsze (nawet 10 linii!) Niż przekształcenie go w DFA. Konrad Rudolph
where is 0 b 3 coming from?: dla wejścia aabbbbcdc przejścia automatu to:(q0, a) = 0, (q0, a) = 0, (q0, b) = 3, (q3, b) = 0, (q0, b) = 3, (q3, b) = 0   'Które chcesz?'; Moja funkcja „Evalu_string” implementuje DFA i chcę wiedzieć, jak go zmodyfikować, aby uzyskać NFA novaKid

Twoja odpowiedź

3   odpowiedź
1

że powinieneś najpierw zaimplementować ogólny mechanizm, aby przekonwertować dowolny NFA do odpowiedniego DFA. Po wykonaniu tej czynności można łatwo zaimplementować biegacz automatyczny, ponieważ DFA działają deterministycznie.

9

Ocena NFA toprawie tak łatwo jak ocenianie DFA.

W DFA masz jeden bieżący stan i na każdym kroku wybierasz następne przejście. Na końcu wejścia sprawdzasz, czy bieżący stan jest stanem akceptacji.

Cóż, w NFA maszzestaw bieżących stanów iw każdym kroku przechodzisz przez wszystkie bieżące stany, a dla każdego wybierzesz wszystkie ważne przejścia. Te połączone zestawy tworzą nowy zestaw stanów.

Na koniec sprawdzasz, czy przecięcie bieżących stanów i stanów akceptacji nie jest puste.

W Pseudo-kodzie wygląda to następująco:

obecny = {Inicjał }dla każdego zwęglać w wkład:Kolejny = {}dla każdego stan w obecny:dla każdego przejście w przejścia[stan] [zwęglać] ∪przejścia[stan] [ϵ]:Kolejny.dodać(cel_of(przejście))obecny = KolejnyJeśli len(skrzyżowanie(obecny, akceptując))> 0:wydrukować "String accepted"jeszcze:wydrukować "String rejected"

To może być przetłumaczone,linia po linii, do kodu C ++. Aby było to łatwe, sugeruję użyciestd::set<int> dlacurrent inext zestawy i wektorstd::multimap<char, int> dla przejść. Zakłada to, że każdy stan odpowiada liczbie całkowitej.

nie jestem pewien, ale myślę, że zestaw „prąd” nie zawiera żadnych elementów na końcu przetwarzania ciągu, dlatego przecięcie między bieżącym a końcowym zestawem jest puste. i zawsze zostanie odrzucony. Teraz nie wiem, czy implementacja zaproponowana przez Konrada Rudolpha jest poprawna, nie widzę w tym żadnej winy. franvergara66
Zmodyfikowałem kod pytania, wprowadziłem zmiany wskazane w odpowiedzi, ale nadal otrzymuję poprawne dane wyjściowe. Co robię źle, wprowadzając swój soluicón ?. Przetłumaczyłem pseudokod na język c + + używając zestawu, jak wskazałeś, ale nadal widzę, co do diabła robię źle. Jakaś pomoc w tej sprawie? novaKid
@ KonradRudolph Nie rozumiem, dlaczego polecasz używanie wektora wektora multimap <multimap <char, int >>, struktura mająca kod będzie działać idealnie. Jaka jest różnica? Przepraszam za nalegania franvergara66
@KonradRudolphfor each transition in transitions[state][char]: next.append(target_of(transition)), Nie rozumiem tych linii, wcięcie jest złe lubnext.append(target_of(transition)) powinien być w pętli? novaKid
1

że twój kod wyłamuje się z pętli przejściowej, gdy tylko znajdziesz PIERWSZE poprawne przejście. Który działałby, gdybyś robił DFA, ale NFA może mieć wiele poprawnych ścieżek.

Dwie opcje, które masz (jestem pewien, że jest ich więcej):

1) Wdrożenie ewaluatora NFA: obejmuje śledzenie zbioru bieżących stanów i ocenę każdego znaku wejściowego w każdym stanie. Po przeczytaniu łańcucha, jeśli którykolwiek ze stanów końcowych znajduje się w zestawie, jest zakończony.

2) Przekonwertuj NFA na DFA, czyli IMHO, tym trudniejsze podejście, ponieważ zasadniczo polega to na zbudowaniu tej samej logiki zestawu i ocenie przejść dla nowych stanów.

@novaKid Przeczytaj post Konrada. Dave S
Hej człowieku, musisz użyć rekursji, aby utworzyć NFA ?. Nie mogę znaleźć drogi, żadnych sugestii poza tym, co mi wskazałeś? novaKid
Jak mogę zmodyfikować kod, aby zrobić to, co wskazałeś w opcji 1)Implement an NFA evaluator. Jest kilka pseudokodów do zrobienia? Mam wiele wątpliwości co do logiki ewaluatora NFA. novaKid

Powiązane pytania