// ntm.cpp  simulate a Nondeterministic Turing Machine
//
// A Turing machine M = (Q, Sigma, Gamma, delta, q0, B, F)
//   where Q is finite set of states including q0
//         Sigma is a finite set of input symbols not including B
//         Gamma is a finite set of tape symbols including Sigma and B
//         delta is a transitions mapping Q X Gamma to Q X Gamma X {L,R,N}
//         q0 is the initial state
//         B is blank tape symbol
//         F is a finite set of final states
//           
// Input Conventions:
//
// the file name extension is typically  .ntm
// free form plain text input file
// typical execution is  ntm < your_input.ntm > 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 five tuple:
// from-state  input-symbol  to-state  symbol-to-write  move
//
// at least one transition is required
// a typical dummy transition is  phi #b phi ## N
//
// special input-symbol #b for the blank character,
//                      #[ for beginning of tape
//                      #] for end of tape
//                      #e for epsilon transition
//
// special symbol-to-write #b for blank character
//                         ## for no character to write
//
// move is L or l for left one space on the tape
//         R or r for right one space on the tape
//         N or n for do not move the tape head
//         anything else becomes "R"
//
// Anything after the required field(s) is a comment
//
// if symbol-to-write is "// "  then the rest of the line
// is a comment and symbol-to-write becomes ##
// and move becomes R, as in a DFA subset of a TM.
//
// if move is  "// "  then move becomes "N" and
// and the rest of the line is treated as a comment
//
// The input and output tape may contain only printable characters
// Use  #b  to input a blank (space) character on the input tape
// If you want a blank on each end of your tape, use #byour-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, input, to-write, tape
//                             note any strangeness
//         build transition map (note: no duplicates means deterministic)
//         initialize tape
//         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 ntm ntm.cpp       or   cl /GX /ML ntm.cpp
// ANSI/ISO C++
// release JSS 1/15/00 v1.0
// mod     JSS 12/5/03 v1.1 fix bug found by g++ 3.2

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <deque>

using namespace std;

static char no_write  = '\0';    // unprintable, do not write
static char epsilon   = '\0';    // unprintable, #e epsilon
static char right_end = '\1';    // unprintable, #] off right end of tape  
static char left_end  = '\2';    // unprintable, #[ off left end of tape

class transition  // 'delta' is the set of these transitions
{
  public:
    transition(string from_state,
               char   input_symbol,
               string to_state,
               char   write_symbol,
               char   move_tape)
               {from=from_state;
               input=input_symbol;
               to=to_state;
               write=write_symbol;
               move=move_tape;}
    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;
    char   write;
    char   move;
};

// a queued nondeterministic transition, along some path
class nd_tran
{
  public:
    nd_tran(){state = ""; tape_position = 0; tape.clear();} 
    nd_tran(string s, int p, vector<char> t)
           {state = s; tape_position = p; tape = t;}
    string state;
    int    tape_position;
    vector<char> tape;
};

int main() //  ntm < 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 = staring state
  set<string>  final;          // F = set of final states
  set<char>    symbols;        // Gamma set of tape symbols
  set<string>  trace;          // set of states to trace 
  vector<char> tape;           // input tape
  vector<transition> t_table;  // delta transitions
  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
  deque<nd_tran> tran_que;     // transition queue
  nd_tran nd_object;           // a popped state, tape_pos, tape
  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 halted = false;      // can not simulate more, halted
  bool halt_mode = false;   // stop upon any '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;        // read/write head position
  int tape_pos_hold;        // read/write head position popped
  char input_char = ' ';    // tape character read
  string next_state;        // transition to next state
  char write_char;          // '\0' means no write
  char move_char;           // move 'L' 'R' 'N'
  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 tm 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 move_tape;        // character extracted later
  string write_symbol;     // character extracted later
  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 #]. right_end
  string write_str;        // temp string for ##, no write

  // 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

  cout << "ntm v1.1 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=="#[") input_symbol[0]=left_end;   // left end
    if(input_symbol=="#]") input_symbol[0]=right_end;  // right end
    if(input_symbol=="#e") input_symbol[0]=epsilon; // epsilon
    cin >> to_state;     if(cin.eof()) break;
    states.insert(to_state);
    to_states.insert(to_state);
    write_symbol=string(1, no_write);
    move_tape="R";
    cin >> check;   if(cin.eof()) break;
    if(check!=comm)
    {
      write_symbol=check;
      if(write_symbol=="#b") write_symbol[0]=' ';      // blank
      if(write_symbol=="##") write_symbol[0]=no_write; // no write
      cin >> check;    if(cin.eof()) break;
      if(check!=comm)
      {
        move_tape=check;
        if(move_tape=="n") move_tape="N";
        if(move_tape=="l") move_tape="L";
        if(move_tape=="r") move_tape="R";
        if(!(move_tape=="L" || move_tape=="R" || move_tape=="N"))
        {
          cout << move_tape << " is not a legal move, set to R" << endl;
          move_tape="R";
        }
      }
    }
    cin.ignore(255,'\n'); // delete trailing comments
    t_table.push_back(transition(from_state, input_symbol[0], to_state,
                      write_symbol[0], move_tape[0]));
    
  } // 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 (five tuples)" << endl;
    no_simulate=true;
  }

  if(!nondeterministic)
  {
    cout << "deterministic 'delta' transition table" << endl;
    cout << "you could use the tm 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" and comment is allowed
      if(!cin.eof() && keyword=="//")
      {
        cin.ignore(255,'\n');
        continue;
      }
      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 set to next_state when popped
    tran_que.push_back(nd_tran(state, tape_position, tape));
    if(debug) cout << "queuing " << state << " at " << tape_position
                   << endl << endl;
    // loop to limit total transition steps                   
    for(step=1; step<limit; step++)
    {
      if(tran_que.empty())
      {
        if(debug) cout << "tran_que is empty" << endl;
        break; // no more transitions available
      }
      nd_object = tran_que.front();
      tran_que.pop_front();
      state = nd_object.state; // restart a path from a nd_object
      tape_pos_hold = nd_object.tape_position;
      tape_position = tape_pos_hold;
      tape = nd_object.tape;
      input_char = tape[tape_position]; // input_char set also at bottom
      if(debug) cout << "popped " << state << " at " << tape_position
                     << " input_char=" << input_char << endl;
                     
      if(trace.size()!=0 && trace.find(state)!=trace.end())
      {
        input_str = input_char;
        if(input_char==epsilon)   input_str="#e";
        if(input_char==right_end) input_str="#]";
        if(input_char==left_end)  input_str="#[";
        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 que next
        tran_que.push_back(nd_tran(t_table[tx].to, tape_position, tape));
        if(debug) cout << "queuing epsilons" << t_table[tx].to << " at "
                       << tape_position << endl;
      }
      
      // check for halt and termination
      if(final.size()!=0 && final.find(state)!=final.end())
      {
        if(input_char==right_end)
        {
           accepted = true;
           if(debug) cout << "terminated and accepted" << endl;
           break; // out of 'step' loop
        }
        else if(halt_mode)
        {
          if(debug) cout << "this path dies, halt mode" << endl;
          continue; // this path dies
        }
      }

      // pull up next normal transition (in loop)
      p_pair = t_index.equal_range(state+input_char);
      if(p_pair.first==t_index.end() || p_pair.first==p_pair.second)
      {
        if(debug) cout << "no more transitions on path" << endl;
        continue; // no more transitions on path
      }

      for(pt=p_pair.first; pt!=p_pair.second && pt!=t_index.end(); pt++)
      {
        tx = pt->second; // restore path state
        next_state=t_table[tx].to;
        write_char=t_table[tx].write;          // may be no_write
        move_char=t_table[tx].move;            // move 'L' 'R' 'N'
        tape_position = tape_pos_hold;
        
        if(write_char!=no_write) // check for no_write to tape (may just move)
        {
          tape[tape_position]=write_char; // write to tape
          if(tape_position==(tape.size()-1)) tape.push_back(right_end);
                            // extend tape to right when writing over right_end
          //if(tape_position==0) tape.push_front(left_end); ??
                            // extend tape to left when writing over left_end
        }
        if(move_char=='L')
        {
          tape_position--;       // move tape
          if(tape_position < 0)
          {
            tape_position=0; // can not move left of left_end
            cout << "attempt to move left of left_end of tape" << endl;
            input_char=left_end;
            break; // out of 'step' loop
          }
        }
        else if(move_char=='R')
        {
          tape_position++;
          if(tape_position>=tape.size())
          {
            tape_position--; // can not move right of right_end
            cout << "attemp to move right of right_end of tape" << endl;
            input_char=right_end;
            break; // out of 'step' loop
          }
        }
        
        tran_que.push_back(nd_tran(next_state, tape_position, tape));
        if(debug)
        {
          cout << "queuing " << next_state << " at "
               << 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 << endl;
       }
      } // finished this batch of nondeterministic transitions
    } // step limit loop
  
  
    // final messages to the user
    if(halted)
    {
      cout << "tm halted after " << step << " steps, at "
           << state << " with output:" << endl ;
      for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
      cout << endl;
    } 
    else if(accepted)
    {
      cout << "tape accepted after " << step << " steps, at " 
           << state << endl ;
      if(debug)
      {
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
      }
    }
    else
    {
      cout << "tape rejected after " << step << " steps" << endl;
      if(debug)
      {
        cout << "tape=";
        for(it=(tape.begin()+1); it!=(tape.end()-1); it++) cout << *it;
        cout << endl;
      }
    }

    initial_tape = "";
    accepted = false;
    tran_que.clear();
    
  }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==epsilon)   input_token=string("#e");
  if(trans.input==right_end) input_token=string("#]");
  if(trans.input==left_end)  input_token=string("#[");
  if(trans.input==' ')       input_token=string("#b");
  string write_token=string(1,trans.write);
  if(trans.write==no_write) write_token=string("##");
  if(trans.write==' ')      write_token=string("#b");
  string move_token=string(1,trans.move);

  stream << trans.from  << '\t' 
         << input_token << '\t'
         << trans.to    << '\t'
         << write_token << '\t'
         << move_token  ;   
  return stream;
}

// end ntm.cpp