Вопросы Теги

Разработка недетерминированного конечного автомата на С++ (неправильный вывод)

Я выполняю задание по моделированию недетерминированного конечного автомата, как я объясняю в этом посте. Я считываю этот ввод из файла 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 
#include 
#include 
#include 
#include 
#include     
using namespace std;

typedef map, char> transitions;
    transitions trans;

    int  numberFinals;
    vector 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 current;
    set next;
    set::iterator it;
    set  final;
    std::set the_intersection;  // Destination of intersect
    map, 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>finalStates;
            final.insert(finalStates);
        }

        for (j=0; j> stateOrigin>>stateDestination>>transitionCharacter;
            trans.insert(transitions::value_type(std::make_pair(stateOrigin, stateDestination), transitionCharacter ));
       }

        cin>>numberInputs;

        cout<<"Test Case #"<> inputString;
            cout<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"<

Мой вопрос: почему я получаю неверный вывод? Я думаю, что это из-за недетерминированности автомата, определенного в тестовом примере, но как я могу правильно оценить строку?Как я могу изменить свою функцию с именем Assessment_stringтак, чтобы она каким-то образом проверяла различные пути, по которым автомат может оценивать строку с помощью недетерминизма?

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

7
задан Community 23 May 2017 в 12:01
поделиться