Design a nondeterministic finite automata in c++ (incorrect output)

Question

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.

Answer 1

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

In a DFA, you have one current state and in each step you select the next transition. At the end of the input, you check whether the current state is an accepting state.

Well, in an NFA you have a set of current states, and in each step you go through all current states, and for each, you select all valid transitions. Those combined sets form your new state set.

At the end, you check whether the intersection of the current states and the accepting states is non-empty.

In Pseudo-code this looks as follows:

• 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"

This can be translated, line by line, into C++ code. To make this easy, I suggest using std::set<int> for the current and next sets, and a vector of std::multimap<char, int> for the transitions. This assumes that each state corresponds to an integer.

Answer 2

I think you should first implement the general mechanism to convert any NFA to its corresponding DFA. After doing that, you can easily implement automaton runner since DFAs work deterministically.

Answer 3

The fundamental problem is that your code is breaking out of the transition loop as soon as you find the FIRST valid transition. Which would work if you were doing a DFA, but an NFA could have multiple valid paths.

Two options you have (I'm sure there are more):

1) Implement an NFA evaluator: This involves keeping track of a set of current states, and evaluating each input character against each state. Once the string has been read, if any of the final states are in the set, it is complete.

2) Convert the NFA to a DFA, which is, IMHO the harder approach, since that basically involves building the same set logic and evaluating the transitions for the new states.