# tm.py turing machine simulator 
#
# A Turing machine M = (Q, Sigma, Gamma, delta, q0, B, F)
#   where Q is finite set of states including q0
#         B includes blank #b, empty ## for no write
#         Sigma is a finite set of input symbols may not include  ##
#         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
#         F is a finite set of final states
#
# Input Conventions: input lines
# "start"  followed by a state name
# "final"  followed by a final state name
# "halt"   followed by a final state name, halt mode
# "trace"  followed by "all" or a state name
# "limit"  followed by an integer, maximum number of transitions
#  transition  from state name, tape symbol, to state name,
#              symbol to write on tape, R L or N to move tape head
# "enddef"  only a "tape" may follow this
# "tape"   followed by a String, may have only single characters
#
#
# the file name extension is typically  .tm
# free form plain text input file
# typical execution is  python tm.py your_input.tm > your_output.out
#
# A comment line has "//" as the first two 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
#
# there is no such thing as a continuation line
#
# A transition is a five tuple:
# from-state  input-symbol  to-state symbol-to-write  RLN
# 
# special input-symbol #b for the blank character, (Not yet)
#                      #e for epsilon transition
#
# at least one transition is required,
# the typical dummy transition is  phi #b phi (not yet)
#
# 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
#
# 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)
#
# run with      python tm.py  xxx.tm

import string
import re
import math
from numpy import array
from sys import argv

# global variables
nmax = 100
states = array([("          ") for i in range(nmax)])
# Q =all named states
nstates = 0
from_states = array([("          ") for i in range(nmax)])
# source states for checking
nfrom_states = 0
to_states = array([("          ") for i in range(nmax)])
# target states for checking
nto_states = 0
start = " "
# q0 = starting state
finals = array([("          ") for i in range(nmax)])
# F = set of final states
nfinals = 0
do_halt = 0
symbols = array([("  ") for i in range(nmax)])
# Sigma = set of tape symbols
nsymbols = 0
trace = array([("          ") for i in range(nmax)])
# states to trace or  "all"
ntrace = 0
trace_all = 0                     # trace all states
tape = "[]"                       # input tape for running
input =  array([("                                          ") for i in range(10)])
# input tapes, maximum of 20
ninput = 0
t_table =  array([[("  ") for j in range(5)] for i in range(nmax)])
# delta = transition table
nt_table = 0
limit = 0
debug = 1 # jons debugging

def add_states(name):
  global states, nstates, debug
  if debug==1 :
    print("add_states(",name,")")

  # end if
  for i in range(nstates) :
    if states[i] == name :
      return

    # end if

  # end for i
  states[nstates] = name
  nstates = nstates+1

# end add_states

def add_finals(name):
  global finals, nfinals, debug
  if debug==1 :
    print("add_finals(",name,")")

  # end if
  add_states(name)
  finals[nfinals] = name
  nfinals = nfinals+1

# end add_finals

def in_final(name):
  global finals, nfinals
  # print("in_final(",name,")")
  for i in range(nfinals) :
    if finals[i] == name :
      return 1

    # end if

  # end for i
  return 0

# end add_finals

def add_trace(name):
  global finals, nfinals
  # print("add_trace(",name,")")
  trace[ntrace] = name
  ntrace = ntrace+1

# end add_trace

def add_to_states(name):
  global to_states, nto_states 
  # print("add_to_states(",name,")")
  for i in range(nto_states) :
    if to_states[i] == name :
      return

    # end if

  # end for i
  to_states[nto_states] = name
  nto_states = nto_states+1

# end add_to_states

def add_from_states(name):
  global from_states, nfrom_states 
  # print("add_from_states(",name,")")
  for i in range(nfrom_states) :
    if from_states[i] == name :
      return

    # end if

  # end for i
  from_states[nfrom_states] = name
  nfrom_states = nfrom_states+1

# end add_from_states

def add_symbols(name):
  global symbols, nsymbols, debug
  if debug==1 :
    print("add_symbols(",name,")")

  # end if
  for i in range(nsymbols) :
    if symbols[i] == name :
      return

    # end if

  # end for i
  symbols[nsymbols] = name
  nsymbols = nsymbols+1

# end add_symbols

def get_transition(fstate, fts) :
  global t_table, nt_table
  for j in range(nt_table) :
    if t_table[j][0]==fstate and t_table[j][1]==fts :
      # an entry in 'alpha' transition_table 
      print("  ",t_table[j][0],"  ",t_table[j][1],"  ",t_table[j][2],
                               "  ",t_table[j][3],"  ",t_table[j][4]),
      return j

    # end if

  # end j
  print("transition not found for ",fstate," l=",len(fstate),"  ",fts," l=",len(fts))
  return -1
  
# end get_transition

def tm(filein):
  global states, nstates, finals, nfinals, t_table, nt_table
  global to_states, nto_states, from_states, nfrom_states
  global start, limit, trace_all, tape, input, ninput, do_halt
  have_enddef = 0
  token = array([("          ") for i in range(20)])  # wrds read
  print("tm running and opening ",filein)
  f2=open(filein,'r')
  print("file opened")
  il = 0 # index of line
  for lline in f2: # reads all lines in file f2
    ll = len(lline)-1
    line = lline[0:ll] # without linefeed, could be zero length
    print(line)
    wrds = line.split()
    if ll<1 :
      continue # skip blank lines

    # end if
    if wrds[0]=="//" :
      continue # skip comments

    # end if
    # print("wrds=",wrds)
    l = len(wrds)
    for i in range(l) :
      token[i] = wrds[i]
          
    if token[0]=="start" :
      add_states(token[1])
      start = token[1]
      
    elif token[0]=="limit" :
      limit = int(token[1])
      
    elif token[0]=="enddef" :
      print("end of tm definition")
      have_enddef = 1

    elif token[0]=="final" :
      add_states(token[1])
      add_finals(token[1])

    elif token[0]=="halt" :
      add_states(token[1])
      add_finals(token[1])
      do_halt = 1

    elif token[0]=="trace" :
      if token[1]=="all" :
         trace_all = 1

      else :
        add_states(token[1])
        add_trace(token[1])

      # end else
      
    # end elif trace
    elif token[0]=="tape" :
      input[ninput] = "["+line[5:ll]+"]"
      ninput = ninput+1
      
    else : # this program requires 5 items on transition
      t_table[nt_table][0] = token[0]
      t_table[nt_table][1] = token[1]
      t_table[nt_table][2] = token[2]
      t_table[nt_table][3] = token[3]
      t_table[nt_table][4] = token[4]
      nt_table = nt_table+1
      add_states(token[0])
      add_from_states(token[0])
      add_symbols(token[1])
      add_states(token[2])
      add_to_states(token[2])
      add_symbols(token[3])
      
    # end else and big if  
    i = i + 1

  # end for line
  f2.close
  if trace_all==1 : # extra printout for debugging and info
    print("input file read")
    print(" ")
    print("start state is: ",start)
    print(" ")
    print("limit on transitions is: ",limit)
    print(" ")
    print("states:")
    for i in range(nstates) :
      print(states[i])

    # end for i
    print(" ")
    print("final states:")
    for i in range(nfinals) :
      print(finals[i])

    # end for i
    if do_halt == 1 :
      print("do_halt set")

    # end if
    print(" ")
    print("trace states:")
    print("trace_all=",trace_all)
    for i in range(ntrace) :
      print(trace[i])

    # end for i
    print(" ")
    print("to states:")
    for i in range(nto_states) :
      print(to_states[i])

    # end for i
    print(" ")
    print("from states:")
    for i in range(nfrom_states) :
      print(from_states[i])

    # end for i
    print(" ")
    print("sigma symbols:")
    for i in range(nsymbols) :
      print(symbols[i])

    # end for i
    print(" ")
    print("transitions:")
    for i in range(nt_table) :
      print(t_table[i][0]," ",t_table[i][1]," ",t_table[i][2],
                          " ",t_table[i][3]," ",t_table[i][4])

    # end for i
    print(" ")
    print("input tapes:")
    for i in range(ninput) :
      print(input[i])

    # end for i
    print(" ")

  # end trace_all  
  print("main simulation loop for each input tape")
  for i in range(ninput) : # process each input tape
    accepted = 0
    finished = 0
    tape = input[i]
    tl = len(tape)-1  # not ] started at 1
    k = 1 # tape head position after [
    print("tm running on input tape: ",tape," tl=",tl)
    state = start
    for lcnt in range(limit) :  # may reaach final or halt
      ts = tape[k:k+1]          # get tape symbol as string
      print("in state=",state,"  tape head at k=",k,"  ts=",ts)
      tj = get_transition(state, ts)
      if tj==-1 :
        break    # transition rule not found

      # print("state=",state,"  ts=",ts," at transition tj=",tj)
      state = t_table[tj][2] # next state
      if in_final(state)==1 and k>=tl-1 :
        accepted = 1
        print(" input tape accepted")
        break           # lcnt

      # end if
      k = k+1    # move tape head
      if k>=tl :
        print(" input tape or tm failed")
        break

      # end if for lcnt

    # end for lcnt
    print(" ")
    print(" ") 
    print(" ")  

  # end i finished last input tape
  print("no more input tapes")

  print("tm.py finished")

# end tm

if __name__=='__main__':
  if len(argv) > 1:
      tm(argv[1]) # read this  .tm file

  else :
      tm("labc.tm")  # for testing


# end tm.py