Разработка недетерминированных конечных автоматов в C++ (неверный вывод)

Question

Я делаю задание для симуляции недетерминированного конечного автомата, как я объясняю в этом посте. У меня есть этот вход читать из файла 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 (переход))
  • текущий = следующий
• if 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, что, ИМХО, является более сложным подходом, поскольку это в основном включает построение одной и той же логики набора и оценку переходов для новых состояний.