Вопрос по c++ – Разработка недетерминированных конечных автоматов в c ++ (неверный вывод)

6

Я делаю задание для моделирования недетерминированного конечного автомата, как я объясняю в этомсообщение, У меня есть этот вход читать из файла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 чтобы каким-то образом проверить разные пути, по которым автомат может оценить строку по недетерминизму?

Я застрял с этим в течение нескольких дней, и, честно говоря, я немного отчаялся.

@KonradRudolph Переходы состояний не имеют значения, я просто печатаю их, чтобы посмотреть, что происходит при каждом изменении состояния, программа просто должна показать, принята или отклонена строка.running the NFA directly is probably easier (not even 10 lines!)Вопрос в том, как я могу это сделать? Я застрял на этом на несколько дней. Как мне изменить свой код, чтобы сделать это? novaKid
Пожалуйста, отформатируйте ваш код в следующий раз. Ваши отступы были далеко. Кроме того, я не понимаю ожидаемого результата. Например, где0 b 3 приходящий из? Наконец, что вы хотите? НФА или ДФА? Ничто в вашем посте не является детерминированным автоматом (ни входом, ни ожидаемым результатом), поэтому я удалил упоминания о & # x201C; DFA & # x201D; сейчас & # x2026; Konrad Rudolph
where is 0 b 3 coming from?: для входа aabbbbcdc переходы автомата:(q0, a) = 0, (q0, a) = 0, (q0, b) = 3, (q3, b) = 0, (q0, b) = 3, (q3, b) = 0   «что вы хотите?»; Моя функция & quot; оценивать_строку & quot; реализует DFA, и я хочу знать, как изменить его, чтобы получить NFA novaKid
Это не то, что я имею в виду.0 b 3 от функции перехода, нет входных данных для рассмотрения. & # X2013; По поводу вашего вопроса: ах, понял. Плохая новость: вы можете преобразовать NFA в DFA и решить его, но вы не можете получить идентичные выходные данные перехода состояния из этого, потому что ваши имена состоянийwill отличаются. Кроме того, запуск NFA напрямую, вероятно, проще (даже не 10 строк!), Чем сначала преобразовать его в DFA. Konrad Rudolph

Ваш Ответ

3   ответа
1

Основная проблема заключается в том, что ваш код выходит из цикла перехода, как только вы найдете ПЕРВЫЙ допустимый переход. Это сработало бы, если бы вы делали DFA, но NFA мог бы иметь несколько допустимых путей.

У вас есть два варианта (я уверен, что их больше):

1) Реализация оценщика NFA: это включает в себя отслеживание набора текущих состояний и оценку каждого входного символа по каждому состоянию. После прочтения строки, если в наборе есть какое-либо из конечных состояний, она завершается.

2) Преобразовать NFA в DFA, что, ИМХО, является более сложным подходом, поскольку это в основном включает построение логики набора и оценку переходов для новых состояний.

Error: User Rate Limit ExceededImplement an NFA evaluatorError: User Rate Limit Exceeded novaKid
1

Я думаю, что вы должны сначала реализовать общий механизм для преобразования любого NFA в соответствующий DFA. После этого вы можете легко реализовать автоматический запуск, поскольку DFA работают детерминистически.

9

Evaluating an NFA is almost as easy as evaluating a DFA.

В DFA у вас есть одно текущее состояние, и на каждом шаге вы выбираете следующий переход. В конце ввода вы проверяете, является ли текущее состояние принимающим.

Ну, в NFA у вас естьset текущих состояний, и на каждом шаге вы проходите все текущие состояния, и для каждого вы выбираете все допустимые переходы. Эти комбинированные наборы формируют ваш новый набор состояний.

В конце вы проверяете, не является ли пересечение текущих состояний и принимающих состояний непустым.

В псевдокоде это выглядит следующим образом:

  • current = { initial }
  • for each char in input:
    • next = { }
    • for each state in current:
      • for each transition in transitions[state][char] ∪ transitions[state][ϵ]:
        • next.append(target_of(transition))
    • current = next
  • if len(intersection(current, accepting)) > 0:
    • print "String accepted"
  • else:
    • print "String rejected"

Это можно перевести,line by lineв код C ++. Чтобы сделать это легко, я предлагаю использоватьstd::set<int> дляcurrent а такжеnext множества и векторstd::multimap<char, int> для переходов. Это предполагает, что каждое состояние соответствует целому числу.

Error: User Rate Limit Exceeded novaKid
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceedednext.insert(p->second);Error: User Rate Limit Exceededp->first.secondError: User Rate Limit Exceededvector<multimap<char, int>>Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded novaKid
Error: User Rate Limit Exceededfor each transition in transitions[state][char]: next.append(target_of(transition))Error: User Rate Limit Exceedednext.append(target_of(transition))Error: User Rate Limit Exceeded novaKid

Похожие вопросы