// tm.java  simulate a Turing Machine
// under development, only single character symbols working
//
// 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
//           
// Speical symbols
// B  or  #b  blank
// ## or  #e  for epsilon, null string, transition
// ]  or  #]  end of string
// [  or  #[  beginning of string
//
// Input Conventions:
//
// the file name extension is typically  .tm
// free form plain text input file
// typical execution is  java tm  your_input.tm > 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, 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
// state name 5 characters or less, input symbol 1 character from alpha
// or special character, like #e,  encoded a one character
//
// special input-symbol #b for the blank character or B
//                      #[ for beginning of tape   or [
//                      #] for end of tape         or ]
//                      #e for epsilon transition  or ##
//
// special symbol-to-write #b or 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.
//
// 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
//
//         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  javac -cp . tm.java 
// run with      java  -cp . tm xxx.tm > xxx_tm.out  (my choice)

import java.io.*;
import java.util.*;
import java.text.*;

public class tm
{
  boolean debug = false;
  boolean dall = false; // e.g. tokens
  // 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

  // primary objects
  int nmax = 100;                           // maximum number of any type 
  String states[] = new String[nmax];       // Q =all named states
  int nstate = 0;
  String from_states[] = new String[nmax];  // source states for checking
  int nfrom_states = 0;
  String to_states[] = new String[nmax];    // target states for checking
  int nto_states = 0;
  String start = "";                        // q0 = starting state
  String finals[] = new String[nmax];       // F = set of final states
  int nfinals = 0;
  String symbols[] = new String[nmax];      // Sigma = set of tape symbols
  int nsymbols = 0;
  String trace[] = new String[nmax];        // states to trace
  int ntrace = 0;  
  boolean trace_all = false;                // trace all states
  String tape = "[]";                       // input tape for running
  String input[] = new String[10];          // input tape, maximum of 10
  int ninput = 0;
  String t_table[][] = new String[nmax][5]; // delta = transition table
  int nt_table = 0;
  String ts;  // tape string  may have #b ## etc.
  char tsch;  // tape character
  int tj = 0; // index to transition
    
  public tm(String filename)
  {  
    // control variables
    int step;                 // transition step
    boolean halt_mode = false;// stop upon entering a 'final' state
    boolean accepted = false; // reached a final state and input right-end
    boolean finished = false; // not accepted, may have error
    String state;             // present state
    int tape_position;        // tape position
    char input_char = ' ';    // tape character read
    String next_state = " ";  // transition to next state
    String prev_from = " ";   // for detecting nondeterministic
    char prev_input = ' ';    // for detecting nondeterministic
    boolean have_enddef = false; // may have to read "tape"
  
    // 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 #]
    boolean feof = false;
    FileReader fin;
    BufferedReader file_in;
    String input_line;
    int ntok;
    StringTokenizer T;
    String token[] = new String[100];
    int limit = 1000;         // max number of transitions (user settable)
    int k = 0; // position of tape head
    
    System.out.println("tm.java starting, reading "+filename);

    try
    {
      fin = new FileReader(filename);
      file_in = new BufferedReader(fin);

      System.out.println("reading "+filename);
      while(true)
      {
        input_line = file_in.readLine();
        if(feof) {break;}
        if(input_line==null) { break; }
        System.out.println(input_line);
        T = new StringTokenizer(input_line," ");
        ntok=0;
        while(T.hasMoreTokens())
        {
          token[ntok]=T.nextToken();
          if(dall) {System.out.println("token["+ntok+"]=|"+token[ntok]+"|");}
          // System.out.println("int="+Integer.parseInt(token[0]));
          // System.out.println("dbl="+Double.parseDouble(token[ntok]));
          // if(token[0].equals("start"))
          ntok++;
        } // end while
        if(dall) {System.out.println("process token[0]="+token[0]);}
	if(token[0].equals("//"))
	{
	  // ignore comment
	}
	else if(token[0].equals(key_start))
	{
	   if(dall){System.out.println("key_start token[0]="+token[0]);}
	   add_state(token[1]);
	   start = token[1];
	} // end else
	else if(token[0].equals(key_final))
	{
	  if(dall) {System.out.println("key_start token[0]="+token[0]);}
	  add_state(token[1]);
	  add_finals(token[1]);
	} // end else
	else if(token[0].equals(key_halt))
	{
	  if(dall) {System.out.println("key_halt token[0]="+token[0]);}
	  add_state(token[1]);
	  add_finals(token[1]);
	  halt_mode = true;
	} // end else
	else if(token[0].equals(key_limit))
	{
	  if(dall) {System.out.println("key_limit token[0]="+token[0]);}
	  limit = Integer.parseInt(token[1]);
	} // end else
	else if(token[0].equals(key_trace))
	{
	  if(dall) {System.out.println("key_trace token[0]="+token[0]);}
          if(token[1].equals("all"))
	  {
	    trace_all = true;
	  }
	  else
	  {
	    add_state(token[1]);
	    add_trace(token[1]);
	  } // end else if
	} // end else
	else if(token[0].equals(key_tape))
	{
	  add_input(token[1]);
        } // end else
	else if(token[0].equals(key_enddef))
	{
	  have_enddef = true;
        } // end else
	
	else // t_table  transition
	{
	  if(ntok<4) { token[4] = "N"; }
	  if(ntok<3) { token[3] = "##"; }
	  add_state(token[0]);
	  add_state(token[2]);
	  add_from_states(token[0]);
	  add_to_states(token[2]);
	  add_symbols(token[1]);
	  add_symbols(token[3]);
	  t_table[nt_table][0] = token[0]; // from state
	  t_table[nt_table][1] = token[1]; // input symbol
	  t_table[nt_table][2] = token[2]; // to state
	  t_table[nt_table][3] = token[3]; // output symbol
	  t_table[nt_table][4] = token[4]; // L, R, or N move
	  nt_table = nt_table+1;
	} // end else if
	
	token[0] = "//"; // handles blank lines
      } // end while
    } // end try
    catch(FileNotFoundException exception)
    {
      System.out.println(filename+" not found");
      System.exit(0);
    } // end catch
    catch(Exception exception) // catches all exceptions
    {
      System.out.println(exception);
      System.out.println("java read_data input-file exception");
      System.exit(0);
    } // end catch try

    System.out.println("reading input finished.");

    // print primary data objects, check for errors and warnings

    if(trace_all)
    {
      System.out.println("start state "+start);
      System.out.println("states:");
      for(int i=0; i<nstate; i++)
      {
        System.out.println(" "+states[i]);
      }
      System.out.println(" ");

      System.out.println("final states:");
      for(int i=0; i<nfinals; i++)
      {
        System.out.println(" "+finals[i]);
      }
      System.out.println(" ");

      System.out.println("trace states");
      for(int i=0; i<nstate; i++)
      {
        System.out.println(" "+states[i]);
      }
      System.out.println(" ");
      for(int i=0; i<ntrace; i++)
      {
        System.out.println(" "+trace[i]);
      }
      System.out.println(" ");

      System.out.println("to_states:");
      for(int i=0; i<nto_states; i++)
      {
        System.out.println(" "+to_states[i]);
      }
      System.out.println(" ");

      System.out.println("from_states:");
      for(int i=0; i<nfrom_states; i++)
      {
        System.out.println(" "+from_states[i]);
      }
      System.out.println(" ");

      System.out.println("sigma symbols:");
      for(int i=0; i<nsymbols; i++)
      {
        System.out.println(" "+symbols[i]);
      }
      System.out.println(" ");

      System.out.println("input tapes:");
      for(int i=0; i<ninput; i++)
      {
        System.out.println(" "+input[i]);
      }
      System.out.println(" ");

      System.out.println("transition table:");
      for(int i=0; i<nt_table; i++)
      {
        System.out.println(" "+t_table[i][0]+
                           "  "+t_table[i][1]+
                           "  "+t_table[i][2]+
                           "  "+t_table[i][3]+
                           "  "+t_table[i][4]);
      }
      System.out.println(" ");
      System.out.println("limit="+limit);
      System.out.println("trace_all="+trace_all);
    } // end if trace_all
    // main simulation loop for each input tape
    for(int i=0; i<ninput; i++) // process each input tape
    {
      accepted = false;
      finished = false;
      tape = input[i]; // #[  #]  added on input
      k = 2; // tape head position
      System.out.println("turing machine running on input tape: "+tape);
      state = start;
      ts = tape.substring(k,k+1); // get tape symbol as string e.g. #b
      if(ts.equals("#")) { ts = tape.substring(k,k+2); }
      tsch = tape.charAt(k);      // get tape symbol as char
      for(int lcnt=0; lcnt<limit; lcnt++) // may reaach final or halt
      {
	if(trace_all || in_trace(state))
	{
	  System.out.println("in state="+state+"  tape head at k="+k+
                             " tape symbol="+ts);
	} // end if
        tj = get_transition(state, ts);
	if(tj==-1)
	{
	  System.out.println("rule not found state="+state+"  ts="+ts);
          break;
	} // transition rule not found
        ts = t_table[tj][3];    // write to tape (fix if length>1) tsch=
        if(trace_all || in_trace(state))
        {
          System.out.println("state="+state+"  write ts="+ts+
			     " at transition tj="+tj);
        } // end if
        state = t_table[tj][2]; // next state
	if(trace_all) { System.out.println("from transition ts="+ts); }
	if(! ts.equals("##"))
        {
	  if(! tape.substring(k,k+1).equals("#"))
	    {tape = tape.substring(0,k)+ts+tape.substring(k+1,tape.length());}
	  else
	    {tape = tape.substring(0,k)+ts+tape.substring(k+2,tape.length());}
	}
	if(in_final(state))
	{
	  if(halt_mode)
	  {
	    accepted = true;
	    break;
	  }
	}
	if(t_table[tj][4].equals("R") || t_table[tj][4].equals("r"))
	{
	  k = k+1;
	  if(trace_all) { System.out.println("move head right to k="+k); }
          tsch = tape.charAt(k);
          ts = tape.substring(k,k+1); // get tape symbol as string e.g. #b
          if(ts.equals("#")) { ts = tape.substring(k,k+2); }
	  if(tsch==']')
	  {
	    k = k-1;
	    System.out.println("can not move right, end of tape, k="+k);
	  } // end if
	} // end if
	if(t_table[tj][4].equals("L") || t_table[tj][4].equals("l"))
	{
	  k = k-1;
	  if(trace_all || in_trace(state))
	  {
	    System.out.println("move head left to k="+k);
	  }
          tsch = tape.charAt(k);      // get tape symbol as char
          ts = tape.substring(k,k+1); // get tape symbol as string e.g. #b
          if(ts.equals("#")) { ts = tape.substring(k,k+2); }
          if(trace_all || accepted)
          {
            System.out.println("tape="+tape+"  head at "+k+" tsch="+tsch+
                               " ts="+ts);
	  } // end if
        } // end if  
      } // lcnt
      if(accepted)
      {
        if(halt_mode)
	{
	  System.out.println("tape="+tape);
	  System.out.println("result tape written");
	}
	else
        {    
          System.out.println(" input tape accepted");
	} // end else
      } // end if accepted
      else if(finished)
      {
	System.out.println(" input tape finished");
      } // end else if
      else
      {
	System.out.println(" input tape or turing machine failed");
      }
      System.out.println(" ");      
      System.out.println(" ");      
      System.out.println(" ");      
    } // end i finished last input tape
    System.out.println("no more input tapes");

    // for outputting objects of class  transition
    //  String input_token=String(1,trans.input);
    //  if(trans.input=='\0') input_token=String("#e"); not used
    //  if(trans.input=='\0') input_token=String("##");                        
    //  if(trans.input=='\1') input_token=String("#]");
    //  if(trans.input=='\2') input_token=String("#[");
    System.out.println(" ");
    System.out.println("finished tm.java");

  } // end of tm

  void add_state(String name)
  {
    for(int i=0; i<nstate; i++)
    {
      if(states[i].equals(name)) return;
    }
    states[nstate] = name;
    nstate = nstate+1;
  } // end add_state

  void add_finals(String name)
  {
    for(int i=0; i<nfinals; i++)
    {
      if(finals[i].equals(name)) return;
    }
    finals[nfinals] = name;
    nfinals = nfinals+1;
  } // end add_final

  void add_trace(String name)
  {
    for(int i=0; i<ntrace; i++)
    {
      if(trace[i].equals(name)) return;
    }
    trace[ntrace] = name;
    ntrace = ntrace+1;
  } // end add_trace

  boolean in_trace(String name)
  {
    for(int i=0; i<ntrace; i++)
    {
      if(trace[i].equals(name)) return true;
    }
    return false;
  } // end in_trace

  void add_from_states(String name)
  {
    for(int i=0; i<nfrom_states; i++)
    {
      if(from_states[i].equals(name)) return;
    }
    from_states[nfrom_states] = name;
    nfrom_states = nfrom_states+1;
  } // end add_from_states

  void add_to_states(String name)
  {
    for(int i=0; i<nto_states; i++)
    {
      if(to_states[i].equals(name)) return;
    }
    to_states[nto_states] = name;
    nto_states = nto_states+1;
  } // end add_to_states

  void add_symbols(String name)
  {
    for(int i=0; i<nsymbols; i++)
    {
      if(symbols[i].equals(name)) return;
    }
    symbols[nsymbols] = name;
    nsymbols = nsymbols+1;
  } // end add_symbols

  void add_input(String name)  // add  [ string ] ?? or use index
  {                            // for movements  L  or  R  or  N
    String sym;
    input[ninput] = "#["+name+"#]"; // input no #[  #]
    ninput = ninput+1;
    for(int i=2; i<name.length()-2; i++) // skip #[ #] 
    {
      sym = name.substring(i,i+1);
      if(sym.equals("#"))
      {
        add_symbols(name.substring(i,i+2));
	i++;
      }
      else
      {
        add_symbols(name.substring(i,i+1));
      }
    } // end i
  } // end add_inout

  int get_transition(String fstate, String fts)
  {
    for(int j=0; j<nt_table; j++)
    {
      if(t_table[j][0].equals(fstate) && t_table[j][1].equals(fts))
      {
	// an entry in 'alpha' transition_table [0] [2] state
	// [1] from alpha, [3] write to tape, [4] L R N move
	if(trace_all)
	{
          System.out.println("   "+t_table[j][0]+"  "+t_table[j][1]+
                     "  "+t_table[j][2]+"  "+t_table[j][3]+"  "+t_table[j][4]);
	}
	return j;  // index to t_table
      } // end if
    } // end j
    System.out.println("transition not found for "+fstate+"  "+fts);
    return -1; 
  } // end get_transition

  boolean in_final(String fstate)
  {
    for(int i=0; i<nfinals; i++)
    {
      if(finals[i].equals(fstate)) { return true; }
    }
    return false;
  } // end in_final

  public static void main(String[] args)
  {
    new tm(args[0]);
  }  
} // end  tm.java