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

Question

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

Первая строка ввода представляет собой целое число Т, представлено число случаев для оценки программы. Каждый тестовый пример начинается с 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 ( переход))
  • тока = следующая
• если 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) Реализовать оценщик НКА: Это включает в себя отслеживание набора текущих состояний, и оценки каждого входного символа с каждого государства. После того, как строка была прочитана, если какое-либо из последних состояний находится в наборе, оно завершено.

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