I am doing an assignment for simulate a nondeterministic finite automaton, just as I explain in this post. I have this input read from the file 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
The first line of input is an integer T, represented the number of cases to evaluate the program. Each test case starts with 4 integers, the first is the number of state for the automaton, next is the number of transitions of the automaton, the third number is the initial state, and then the number of final states. then come the final states (in the example the final states are 2 and 5). Then come F lines, each with an integer E, representing E is a final state.
Then come N lines (N is the number of transitions), each with 2 integers and a character, I, J and C, representing the states where the transition, ie, the transition goes from state i to state J with the character C. Following this line come with a single integer S, which will contain the number of strings to test, then S lines with the respective strings.
the expected output is:
Test Case #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted
The output resulting in my code:
Test Case #1:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Rejected
abc Rejected
Here's my code:
#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;
}
My question is: Why do I get incorrect output? I think it is for the nondeterminism of the automaton defined in the test case, but how I can evaluate the string correctly?. How I can change my function called evaluate_string
to that in some way check the different paths that can take the automaton to evaluate the string by the non-determinism?
I've been stuck with this for several days and to be honest I am somewhat desperate about.