title: Design a nondeterministic finite automata in c++ (incorrect output)
body: <p>I am doing an assignment for simulate a nondeterministic finite automaton, just as I explain in this <a href="https://stackoverflow.com/questions/10579348/implementing-a-code-to-simulate-a-finite-automaton-nondeterministic-in-c">post</a>. I have this input read from the file <code>tarea4.in</code>:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>the expected output is: </p>
  
  <pre><code>Test Case #2:
  aaabcccc Rejected
  aabbbbcdc Rejected
  abbcdddcc Rejected
  acdddddd Accepted
  abc Accepted
  </code></pre>
  
  <p>The output resulting in my code:</p>
  
  <pre><code>Test Case #1:
  aaabcccc Rejected
  aabbbbcdc Rejected
  abbcdddcc Rejected
  acdddddd Rejected
  abc Rejected
  </code></pre>
  
  <p>Here's my code: </p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;vector&gt;
  #include &lt;map&gt;
  #include &lt;set&gt;
  #include &lt;utility&gt;
  #include &lt;vector&gt;    
  using namespace std;
  
  typedef map&lt;pair&lt;int, int&gt;, char&gt; transitions;
      transitions trans;
  
      int  numberFinals;
      vector&lt;int&gt; 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&lt;int&gt; current;
      set&lt;int&gt; next;
      set&lt;int&gt;::iterator it;
      set &lt;int&gt; final;
      std::set&lt;int&gt; the_intersection;  // Destination of intersect
      map&lt;pair&lt;int, int&gt;, char&gt;::iterator p;
      string inputString;
  
      cin&gt;&gt; testCases;
      for (i=0;i&lt; testCases;i++){
          cin&gt;&gt;numberStates&gt;&gt;numberTransitions&gt;&gt;initialState&gt;&gt;numberFinals;
          current.insert (initialState);
  
          for (j=0;j&lt;numberFinals;j++){
              cin&gt;&gt;finalStates;
              final.insert(finalStates);
          }
  
          for (j=0; j&lt;numberTransitions;j++){
              cin&gt;&gt; stateOrigin&gt;&gt;stateDestination&gt;&gt;transitionCharacter;
              trans.insert(transitions::value_type(std::make_pair(stateOrigin, stateDestination), transitionCharacter ));
         }
  
          cin&gt;&gt;numberInputs;
  
          cout&lt;&lt;"Test Case #"&lt;&lt;cont++&lt;&lt;":"&lt;&lt;endl;    
  
          for (j=0; j&lt;numberInputs;j++){
               //////////////////the code of the answer /////////////////
              current.insert (initialState);
              cin&gt;&gt; inputString;
              cout&lt;&lt;inputString&lt;&lt;" ";
  
  
       for (k=0; k&lt;str.size();k++){
           next.clear();
           for ( it=current.begin() ; it != current.end(); it++ ){
                for (q= trans.begin(); q!= trans.end();q++){
                    if((*it == q-&gt;first.first)&amp;&amp;(str[k]==q-&gt;second)){
                       next.insert(q-&gt;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()&gt;0){
                  cout&lt;&lt; "Accepted"&lt;&lt;endl;
              }
              else{
                  cout&lt;&lt; "Rejected"&lt;&lt;endl;
              }
  
          }
  
          printf ("\n");
      }
  
  return 0;
  }
  </code></pre>
  
  <p>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 <code>evaluate_string</code> to that in some way check the different paths that can take the automaton to evaluate the string by the non-determinism?</p>
  
  <p>I've been stuck with this for several days and to be honest I am somewhat desperate about. </p>