// Demonstration of a simple finite state automata
// Bugs: not user friendly or safe to use.
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <utility>
#include <map>
#include <set>

using namespace std;

int main()
{
  //Abstract definition of a DFA
   typedef int Q; //a finite set of states
   typedef char Sigma; // a set set of inputs
   map< pair<Q,Sigma> , Q> delta; // a transition function;
                                  // delta[make_pair(q,i)] == next q
   Q start; 
   set<Q> F; // set of final states, initially empty.

  // example in section 2.2.2
   start = 0;
   delta[make_pair(0,'0')]=2;   delta[make_pair(0,'1')]=0;
   delta[make_pair(1,'0')]=1;   delta[make_pair(1,'1')]=1;
   delta[make_pair(2,'0')]=2;   delta[make_pair(2,'1')]=1;
   F.insert(1);

  /* Debug Table
   for( map< pair<Q,Sigma>, Q>::const_iterator p = delta.begin();
	p != delta.end();
	++p )
   {
     cout << p->first.first << " "<< p->first.second<<" "<< p->second <<endl;
   }//for
  */

  // Run the automata defined above
   Q q=start;
   char a; //the next input supplied by the user
   cout << "State="<<q<<(F.count(q)?" Accept":" Reject") <<endl<<"Input=? ";
   while(cin >> a)
   {
      Q old=q;
      q=delta[make_pair(q,a)];
      cout << "Old = "<<old<<" Input = '"<<a<<"', State="<<q<<(F.count(q)?" Accept":" Reject")
                      <<endl<<"Input=? ";
   }//while

   return 0;

}