## Turing Machine Emulator (3/10-08)
## Made by S. Juul (zpon.dk@gmail.com - www.zpon.dk/blog/?page_id=103)
## Released under GPL
##
## CREDITS:
## --test1 and --test2 is found in the book "Introduction to the Theory of Computation" of Michael Sipser (http://www-math.mit.edu/~sipser/book.html)
##
## TM FILES:
## All lines start with the name of the state (e.g. q1) plus a colon ":", the followed with a number of transactions from the state to others.
##
## The transactions is build in the form <symbole> "->" <symbole> "[" <direction> "]" <statename>
## <symbole> can not be blank = " ", instead use underscore "_". <direction> can be r (right) or l (left).
## <statename> can be a name of the states to be defined or already defined, or to accept or reject. Transactions not defined will automatically go to reject.
## Here is an example: "_->2[r]q1" of a transaction which, if the tape head is on "_" writes "2" and moves right and goes to state "q1"
##
## Note that states accept and reject should not be defined. Also note that the first defined state will be the start state.
##
## EXAMPLE:
## q1: _->[r]reject x->[r]reject 0->_[r]q2
## q2: x->[r]q2 _->[r]accept 0->x[r]q3
## q3: x->[r]q3 0->[r]q4 _->[l]q5
## q4: 0->x[r]q3 x->[r]q4 _->[r]reject
## q5: 0->[l]q5 x->[l]q5 _->[r]q2

import sys
class Transaction:
        # (string)+"->"(string)* "[" ("r" | "l") "]" "q" number
        readValue = ""
        writeValue = ""
        direction = ""
        state = ""
	
        def __init__(self, string):
		string = string.lstrip()
		self.readValue = string[0:string.index('->')]
		string = string[string.index('->')+2:len(string)]
	
		if string.index("[") == 0:
       	                self.writeValue = self.readValue
		elif string.index("[") != -1 and string.index("[") > 0:
			self.writeValue = string[0:string.index("[")]

                self.direction = string[string.index("[")+1 : string.index("]")]
		if self.direction != "l" and self.direction != "r":
			print "\n\tERROR in TM: only r (right) and l (left) for example 0->1[l]q1 you used: " + self.direction + "\n"
			exit()
       	        self.state = string[string.index("]")+1:len(string)]
              
	## Get read value
	def getReadValue(self):
		return self.readValue
	
	## Get write value
	def getWriteValue(self):
		return self.writeValue
	
	## Get state
	def getState(self):
		return self.state
	
	## Get direction
	def getDirection(self):
		return self.direction


class State:
	## Initiate object with name
	def __init__(self, name):
		self.name = name		# name of state
		self.transactions = []		# array of transactions
	
	## Add transaction to array
	def addTransaction(self, transaction):
		self.transactions.append(transaction)
	
	def findTransaction(self, headSymbole):
		returnSymbole = ""
		returnState = ""
		returnDirection = ""
		for trans in self.transactions:
			if trans.getReadValue() == headSymbole:
				returnSymbole = trans.getWriteValue()
				returnState = trans.getState()
				returnDirection = trans.getDirection()
				break
		if returnSymbole == "":
			returnSymbole = headSymbole
			returnState = "reject"
			returnDirection = "l"
			
		return returnSymbole, returnState, returnDirection
	
	## Return name of state
	def getName(self):
		return self.name


tm = ""
tape = ""
help = """Turing Machine Emulator (zpon.dk@gmail.com - http://zpon.dk/blog/?page_id=103)

Usage -f <filename> -i <input>

--file/-f <file>\tRead file
--input/-i <input>\tuser defined input to the TM
--test1 \t\taccepts 0^2^n for example \"0000\"
--test2 \t\taccepts w#w where w = (1 | 0)* - w is the same on both sides
--help/-h \t\tPrint this

For help on the input files, read the top of tm.py"""
printHelp = False

i = 1
while i < len(sys.argv):
	if sys.argv[i] == "--test1":
		# accepts 0^2^n
		tm = """q1: _->[r]reject x->[r]reject 0->_[r]q2
		q2: x->[r]q2 _->[r]accept 0->x[r]q3
		q3: x->[r]q3 0->[r]q4 _->[l]q5
		q4: 0->x[r]q3 x->[r]q4 _->[r]reject
		q5: 0->[l]q5 x->[l]q5 _->[r]q2"""
		tape = "00000000000000000000000000000000"
	elif sys.argv[i] == "--test2":
		# accepts w#w where w = (1 | 0)* - w is the same on both sides
		tm = """q1: #->[r]q8 1->x[r]q3 0->x[r]q2
		q2: 0->[r]q2 1->[r]q2 #->[r]q4
		q3: 0->[r]q3 1->[r]q3 #->[r]q5
		q4: x->[r]q4 0->x[l]q6
		q5: x->[r]q5 1->x[l]q6
		q6: 0->[l]q6 1->[l]q6 x->[l]q6 #->[l]q7
		q7: 0->[l]q7 1->[l]q7 x->[r]q1
		q8: x->[r]q8 _->[r]accept"""
		tape = "01111100#01111100"
	elif sys.argv[i] == "--input" or sys.argv[i] == "-i":
		tape = sys.argv[i+1]
		i += 1
	elif sys.argv[i] == "--file" or sys.argv[i] == "-f":
		print "Reading " + sys.argv[i+1]
		f=open(sys.argv[i+1], 'r')
		tm = f.read()
		i += 1
	elif sys.argv[i] == "--help" or sys.argv[i] == "-h":
		printHelp = True
	else:
		print "\n\tERROR: Parameter not understood: " + sys.argv[i] + "\n"
		exit()
		
	i += 1
		
## No Turing machine defined
if tm == "" or printHelp:
	print help
## No tape content
elif tape == "" and not printHelp:
	print "\n\tERROR: You need to define what the tape contains at the start, use --input <input>\n"
	exit()
## All's good, go ahead
else:
	currentStateName = ""
	currentHeadPosition = 0

	scheme = {}

	## Analyse given Turing Machine
	for line in tm.splitlines():
		seperatorIndex = line.find(':')
		if(seperatorIndex == -1):
			print "Fejl - du mangler \":\" efter state name"
		else:
			stateName = line[0:seperatorIndex].lstrip()
			
			for s in scheme.keys():
				if s == stateName:
					print "\n\tERROR: the state " + stateName + " is already defined, and cannot be defined twice\n"
					exit()

			state = None
			scheme[stateName] = State(stateName)
			if currentStateName == "":
				currentStateName = stateName
			line = line[seperatorIndex+1:len(line)].lstrip()
			transactions = []
			for transaction in line.split(' '):
				scheme[stateName].addTransaction(Transaction(transaction))
	
	print """c = current tape value
w = write value to tape
d = direction
t = tape content
s = move to state
"""

	## Run TM
	while currentStateName != "reject" and currentStateName != "accept":
		if len(tape)-1 < currentHeadPosition:
			currentValue = "_"
		else:
			currentValue = tape[currentHeadPosition]
	
		currentState = scheme[currentStateName]
	
		writeSymbole, nextState, direction = currentState.findTransaction(currentValue)

		print "c " + currentValue + " w "  + writeSymbole + " d " + direction + " t " + tape + " s " + nextState

		tape = tape[0:currentHeadPosition] + writeSymbole + tape[currentHeadPosition+1:len(tape)]
	
		currentStateName = nextState
	
		if direction == "l":
			if currentHeadPosition == 0:
				currentHeadPosition = 0
			else:
				currentHeadPosition -= 1
		else:
			currentHeadPosition += 1
		
	if currentStateName == "accept":
		print "\nACCEPT"
		print "Tape: " + tape
	else:
		print "\nREJECT"
		print "Tape: " + tape