// nfa.cpp  simulate a Nondeterministic Finite Automata
//
// Machine definition of a NFA  M = (Q, Sigma, alpha, q0, F)
//    where Q is set of states
//          Sigma is input tape alphabet
//          alpha is transition table
//          q0 is the starting state
//          F is the set of final states
//
// Input Conventions:
//
// the file name extension is typically  .nfa
// free form plain text input file
// typical execution is   nfa < your_input.nfa > your_output.out
//
// A comment line has "// " as the first three characters
// A line may end with a comment using whitespace "//"
// Anything after whitespace after last expected input is a comment
//
// There are only a few keywords:
//                 start, final, halt, trace, limit, enddef and tape
// any line not starting with these keywords is a transition
// 'enddef' is only needed when more than one 'tape' is to be read
//
// there is no such thing as a continuation line
//
// A transition is a three tuple:
// from-state  input-symbol  to-state
// 
// special input-symbol #b for the blank character,
//                      #e for epsilon transition
//
// at least one transition is required,
// the typical dummy transition is  phi #b phi
//
// Anything after the required field(s) is a comment
//
// Use  #b  to input a blank (space) character on the input tape
// If you want a blank on the end of your tape, use  your-stuff#b
// The initial position will point to your first tape character
// #] will be appended as a right_end character
// #[ will be appended as a left_end character
//
// Method: accumulate states, do consistency checking
//         accumulate symbols, note any strangeness
//         build transition map (note: no duplicates means deterministic)
//         run from start-state
//         trace as user requests
//         accept or reject (also halt feature)
//
// This is one of a series of automata simulators
// dfa  deterministic finite automata (with epsilon transitions and halt)
// nfa  nondeterministic finite automata
// tm   Turing machine, deterministic (recognizer and function computation)
// ntm  nondeterministic Turing machine (language recognizer only)
//
// compile with  GNU g++  2.8.1 or later  or   Microsoft 6.0 or later
//               g++ -o nfa nfa.cpp       or   cl /GX /ML nfa.cpp
// ANSI/ISO C++
// release JSS 1/15/00 v1.0

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>
using namespace std;

  class transition // an entry in 'alpha' transition_table 
  {
    public:
      transition(string from_state,
                 char   input_symbol,
                 string to_state)
                 {from=from_state;
                 input=input_symbol;
                 to=to_state;}
      static bool smaller(transition a, transition b)
                     { if(a.from<b.from) return true;
                       else if(a.from>b.from) return false;
                       else return a.input<b.input; }
      friend ostream &operator<<(ostream &stream, transition trans);
      string from;
      char   input;
      string to;
  };
  

int main() //  nfa < input-file > output-file
{
  // primary objects
  set<string>  states;         // Q =all named states
  set<string>  from_states;    // source states for checking
  set<string>  to_states;      // target states for checking
  string       start = "";     // q0 = starting state
  set<string>  final;          // F = set of final states
  set<char>    symbols;        // Sigma = set of tape symbols
  set<string>  trace;          // states to trace
  vector<char> tape;           // input tape
  vector<transition> t_table;  // alpha = transition table
  typedef pair<string, int> c_index; // to make t_index 
  typedef multimap<string, int, less<string> > t_map;
  t_map t_index;               // t_table index
  typedef pair<string, int> nd_tran; // (state, tape_position) 
  deque<nd_tran> tran_que;     // transition queue
  nd_tran nd_object;           // a popped state, tape_position
  pair<t_map::iterator, t_map::iterator> p_pair; // for t_index
  
  // primary iterators  
  vector<transition>::const_iterator x;      // for t_table
  int tx;                                    // for t_table
  t_map::iterator pt;                        // for t_index
  set<string>::const_iterator        iter;   // for sets
  set<string>::const_iterator        iter2;  // for sets
  vector<char>::iterator             it;     // for tape
  string::iterator                   its;    // for string
  
  // control variables
  int limit = 10000;        // max number of transitions (user settable)
  int step;                 // transition step
  bool halt_mode = false;   // stop upon entering a 'final' state
  bool accepted = false;    // reached a final state and input right-end
  bool no_simulate = false; // set true by various errors
  string state;             // present state
  int tape_position;        // tape position
  char input_char = ' ';    // tape character read
  string next_state = " ";  // transition to next state
  int i;                    // loop index
  string prev_from = " ";   // for detecting nondeterministic
  char prev_input = ' ';    // for detecting nondeterministic
  bool have_enddef = false; // may have to read "tape"
  bool nondeterministic = false; // use the dfa simulator
  bool debug = false;       // for development debugging
  
  // input variables
  string keyword;          // for inputting candidate keyword
  string from_state;       // for inputting one from_state
  string input_symbol;     // character extracted later
  string to_state;         // for inputting one to-state
  string final_state;      // for inputting one final or halt state
  string trace_state;      // for inputting one trace_state
  string initial_tape =""; // check for #b (may read more than 1)
  string check;            // check for // that ends data on a line
  string input_str;        // temp string for #]
  
  // keywords and special symbols
  string key_start = "start";  // followed by a state
  string key_tape  = "tape";   // followed by a string, may have #b
  string key_final = "final";  // followed by a final state name
  string key_halt  = "halt";   // followed by a final state name, halt mode
  string key_trace = "trace";  // followed by "all" or a state
  string key_limit = "limit";  // followed by an integer
  string key_enddef= "enddef"; // only a "tape" may follow this
  string comm      = "//";     // start comment
  string empty     = "";       // empty string
  char epsilon   = '\0';       // unprintable, #e epsilon
  char right_end = '\1';       // unprintable, #] off right end of tape
  char left_end  = '\2';       // unprintable, #[ off left end of tape
  
  cout << "nfa v1.0 starting" << endl;

  while(!cin.eof()) // main input loop
  {
    cin >> keyword;
    if(cin.eof()) break;
    if(keyword==key_start)
    {
      if(start!=empty) cout << "Over writing a previous start state."
                         << endl;
      cin >> start;
      states.insert(start);
      if(start=="//") cout << "start looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_tape)
    {
      cin >> initial_tape;
      if(initial_tape=="//") initial_tape="";
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_final)
    {
      cin >> final_state;
      final.insert(final_state);
      if(final_state=="//") cout << "final looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_halt)
    {
      halt_mode = true; // halt upon entering any final state
      cin >> final_state;
      if(final_state!=comm && final_state!=empty)
      {  // allow stand alone "halt" just to set flag
        final.insert(final_state);
      }
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_trace)
    {
      cin >> trace_state;
      trace.insert(trace_state);
      if(trace_state=="//") cout << "trace state looks like a comment?" << endl;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_limit)
    {
      cin >> limit;
      cin.ignore(255,'\n');
      continue;
    }
    else if(keyword==key_enddef) // stop inputting
    {                            // now may only read "tape"
      cin.ignore(255,'\n');
      have_enddef = true;
      break;
    }
    else if(keyword=="//") // skip comment "// "
    {
      cin.ignore(255,'\n');
      continue;
    }
    else
    {
      from_state = keyword;
      states.insert(from_state);
      from_states.insert(from_state);
    }
    cin >> input_symbol; if(cin.eof()) break;
    if(input_symbol=="#b") input_symbol[0]=' ';        // a space
    if(input_symbol=="#e") input_symbol[0]=epsilon;    // epsilon
    if(input_symbol=="#]") input_symbol[0]=right_end;  // right end
    
    cin >> to_state;     if(cin.eof()) break;
    states.insert(to_state);
    to_states.insert(to_state);
    cin.ignore(255,'\n'); // delete trailing comments
    t_table.push_back(transition(from_state, input_symbol[0], to_state));
    
  } // end main input loop

  cout << "reading input finished." << endl;

  // print primary data objects, check for errors and warnings
  if(states.size()==0)
  {
    cout << "No states input prevent simulation. Stopping." << endl;
    return 1;
  }

  cout << "start state " << start << endl;

  cout << "states:";
  for(iter=states.begin(); iter!=states.end(); iter++) cout << *iter << " ";
  cout << endl;

  iter = from_states.find(start); // check that start is a legal state
  if(iter==states.end())
  {
    cout << start << " is not a legal starting state." << endl;
    no_simulate=true;
  }
  cout << endl;
  
  cout << "final states:";
  if(final.size()==0)
  {
    cout << "   No final states" << endl;
  }
  else if(to_states.size()!=0)
  {
    for(iter=final.begin(); iter!=final.end(); iter++) cout << *iter << " ";
    cout << endl;

    for(iter=final.begin(); iter!=final.end(); iter++) // check final states
    {
      iter2 = to_states.find(*iter);
      if(iter2==to_states.end() && (*iter!=start))
      {
        cout << *iter << " is not a valid final state." << endl;
        no_simulate=true;
      }
    }
    cout << endl;
  }

  if(trace.size()==1 && *trace.begin() == "all") trace = states;
  cout << "trace states:";
  if(trace.size()==0)
  {
    cout << "No states to trace" << endl;
  }
  else
  {
    for(iter=trace.begin(); iter!=trace.end(); iter++) cout << *iter << " ";
    cout << endl << endl;

    for(iter=trace.begin(); iter!=trace.end(); iter++) // check trace states
    {
      iter2 = states.find(*iter);
      if(iter2==states.end())
      {
        cout << *iter << " is not a valid trace state." << endl;
      }
    }
    cout << endl;
  }

  if(t_table.size()!=0)
  {
    sort(t_table.begin(), t_table.end(), transition::smaller );
    cout << "Sorted transition table:" << endl;
    for(x=t_table.begin(); x!=t_table.end(); x++)
    {
      cout << *x << endl;
      if(x->from==prev_from && (x->input==prev_input ||
         prev_input==epsilon))
      {
        nondeterministic = true;
      }
      prev_from=x->from;
      prev_input=x->input;
    }
  }
  else
  { 
    cout << "No transitions (three tuples)" << endl;
    no_simulate=true;
  }

  if(!nondeterministic)
  {
    cout << "deterministic 'alpha' transition table" << endl;
    cout << "you could use the dfa simulator" << endl;
  }
  if(no_simulate)
  {
    cout << "Errors in input prevent simulation. Stopping." << endl;
    return 1;
  }

  // build map for state+input_character to transition table index
  for(tx=0; tx<t_table.size(); tx++)
  {
    t_index.insert(c_index(t_table[tx].from+t_table[tx].input, tx));
  }
  

  // main simulation loop for each tape
  do // may read zero or more "tape" lines
  {
    if(initial_tape.size()==0 && have_enddef) // expect to read a "tape"
    {
      cin >> keyword; // only "tape" is allowed
      if(!cin.eof() && keyword==key_tape)
      {
        cin >> initial_tape;
        if(initial_tape=="//") initial_tape = ""; // null tape
        cin.ignore(255,'\n');
      }
      else
      {
        cout << " No more input tapes. Stopping." << endl;
        return 1;
      }
    }
    
    // clean up initial_tape into tape
    tape.clear(); // may come around again
    tape.push_back(left_end); // force known beginning of tape
    for(its=initial_tape.begin(); its!=initial_tape.end(); its++)
    {
      if((its+1)!=initial_tape.end())
      {
        if(*its=='#' && *(its+1)=='b')
        {
          tape.push_back(' ');
          its++;
        }
        else
        {
          tape.push_back(*its); // allows '#' sometimes    
        }
      }
      else
      {
        tape.push_back(*its);        
      }
    }
    tape.push_back(right_end); // force known end of tape
    tape_position = 1; // start past #[ on first user character
    cout << endl << "tape = ";
    for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
    cout << endl; // do not print the left_end and right_end
  
    state=start;          // state and tape_position into tran_que
    tran_que.push_back(nd_tran(state, tape_position));
    if(debug)cout << "queuing " << state << " at " << tape_position << endl;
    for(step=1; step<limit; step++)
    {
      if(tran_que.empty()) break; // no more transitions available
      nd_object = tran_que.front();
      tran_que.pop_front();
      state = nd_object.first;
      tape_position = nd_object.second;
      if(debug)cout << "popped " << state << " at " << tape_position << endl;
      input_char = tape[tape_position]; // input_char set also at bottom
      if(trace.size()!=0 && trace.find(state)!=trace.end())
      {
        input_str = input_char;
        if(input_char==right_end) input_str = "#]";
        if(input_char==epsilon) input_str = "#e";
        cout << "step " << step << "  " << state << "  "
             << input_str << " at pos " << tape_position << endl;
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
        cout << "    ";
        for(i=0; i<tape_position; i++) cout << ' ';
        cout << '^' << endl;
      }
  
      // test for epsilon transition first
      p_pair = t_index.equal_range(state+epsilon);
      for(pt=p_pair.first; pt!=p_pair.second && pt!=t_index.end(); pt++)
      {
        tx = pt->second; // process epsilon transitions, just queue next state
        tran_que.push_back(nd_tran(t_table[tx].to, tape_position));
        if(debug)cout << "queuing " << t_table[tx].to << " at "
                      << tape_position << endl;
      }
  
      // check for termination
      if(final.size()!=0 && final.find(state)!=final.end())
      {
        if(input_char==right_end)
        {
           accepted = true;
           break; // out of 'step' loop
        }
        else if(halt_mode)
        {
           continue; // this path dies
        }
      }
      if(input_char==right_end)
      {
         continue; // this path dies
      }
  
  
      // pull up next normal transition
      p_pair = t_index.equal_range(state+input_char);
      if(p_pair.first==t_index.end()) continue; // no more transitions on path
      
      for(pt=p_pair.first; pt!=p_pair.second && pt!=t_index.end(); pt++)
      {
        tx = pt->second; // process this nd group
        tape_position++;
 
        next_state=t_table[tx].to;
       
        if(debug)cout << "transition to state=" << next_state << endl;
  
        if(tape_position>=tape.size()) // bug catcher, should not happen
        {
          continue; // this path dies
        }
      
        tran_que.push_back(nd_tran(next_state, tape_position));
        if(debug)cout << "queuing " << next_state << " at "
                      << tape_position << endl;
        tape_position--; // reset for next in loop
      } // finished this batch of nondeterministic transitions
    } // step limit loop, go for next transition
  
  
    // final messages to the user
    if(accepted)
    {
      cout << "tape accepted after " << step << " steps, at " 
           << state << endl ;
    }
    else
    {
      cout << "tape rejected after " << step << " steps" << endl;
    }
    initial_tape = "";
    accepted = false;
  
  }while(!cin.eof() && have_enddef); // close out tape read 'do'

  return 0;
} // end of main

// for outputting objects of class  transition
ostream &operator<<(ostream &stream, transition trans)
{
  string input_token=string(1,trans.input);
  if(trans.input=='\0') input_token=string("#e");
  if(trans.input=='\1') input_token=string("#]");
  if(trans.input=='\2') input_token=string("#[");
  
  stream << trans.from  << '\t' 
         << input_token << '\t'
         << trans.to    << '\t' ;   
  return stream;
}

// end nfa.cpp