import sys,os,json,pprint


class PDA():
	"""
	Represents a Push-Down Automaton
	"""
	EPSILON = '_e'
	MAX_STEPS = 10000

	def __init__(self):
		pass
		
	def testAutomata(self, pda, testcases):
		"""
		Tests whether the given PDA accepts or rejects the given testcases appropriately
		
		Args:
			* pda: PDA object to be tested
			* testcases: Strings used for testing the PDA
		
		Returns:
			The result from simulating the PDA with the given inputs::

				{'result': True} -- The PDA ran correctly with every input
				{'result': False, 'minimal': 'aabb'} -- The PDA did not run correctly on input aabb
		"""
		if type(testcases) != dict or len(testcases) == 0:
			return { 'result': False, 'minimal': 'No testcases defined' }
		cases = sorted(sorted(testcases.keys()), key=len) # Order by length, alphabetic
		for string in cases:
			wanted = testcases[string]
			simulate = self.simulate(pda, string)
			if wanted != simulate:
				return { 'result': False, 'minimal': string }
		return { 'result': True }
			
	def simulate(self, pda, string):
		"""
		Simulates the execution of PDA on a given input
		
		Args:
			* pda: PDA object to be executed
			* string: Input to be simulated
		
		Returns:
			| True, if the PDA accepts the string
			| False, if not
		"""
		visited = set()
		queue = [(pda['start'], "", 0)] # Current state, stack, input string index
		n = 0
		
		while len(queue) != 0:
			current = queue.pop(0)
			visited.add(current)
			curState,curStack,curIndex = current
			if curState in pda['accepting'] and curIndex == len(string):
				return True
			if curIndex < len(string):
				nextInput = string[curIndex]
			else:
				nextInput = None
			n += 1
			if n > PDA.MAX_STEPS:
				break
			for transition in pda['transitions'][curState]:
				inputSymbol,popStack,pushStack = transition.split(',')
				nextStates = pda['transitions'][curState][transition]
				nextStack = curStack
				nextIndex = curIndex
				valid = True
				if inputSymbol == PDA.EPSILON or inputSymbol == nextInput:
					if popStack != PDA.EPSILON:
						if curStack[-1] == popStack:
							nextStack = curStack[0 : len(curStack)-1]
						else:
							valid = False
					if pushStack != PDA.EPSILON:
						nextStack += pushStack
					if inputSymbol != PDA.EPSILON:
						nextIndex = curIndex+1
					if valid:
						for state in nextStates:
							nextItem = (state, nextStack, nextIndex)
							if nextItem not in visited:
								queue.append(nextItem)
		return False

if __name__ == '__main__' and sys.argv[1] and sys.argv[2]:

	pp = pprint.PrettyPrinter(indent=4)
	comp = PDA()
	automata = json.loads(open(sys.argv[1], 'r').read())
	#pp.pprint( automata )
	print comp.simulate(automata, sys.argv[2])



