half_language.py

from collections import defaultdict

class StateMachine:

	def initial_state(self):
		raise NotImplementError()

	def accept(self, state):
		raise NotImplementError()

	def transitions(self, state):
		raise NotImplementError()

	def transition(self, state, letter):
		for (tlet, dest) in self.transitions(state):
			if tlet == letter:
				return dest
		raise "Undefined transition"

	def match(self, s):
		state = self.initial_state()
		print "--", s
		for c in s:
			print c
			state = self.transition(state, c)
			print state
		return self.accept(state)



class SimpleStateMachine(StateMachine):

	def __init__(self, initial_state, transitions, accept):
		self._initial_state = initial_state
		self._transitions = transitions
		self._accept = accept

	def initial_state(self):
		return self._initial_state

	def accept(self, state):
		return state in self._accept

	def transitions(self, state):
		return self._transitions[state]


# # a(aba)*
# simple_state_machine = SimpleStateMachine(1, {
# 	1: [("a", 2), ("b", 4)],
# 	2: [("a", 3), ("b", 4)],
# 	3: [("a", 4), ("b", 2)],
# 	4: [("a", 4), ("b", 2)],
# 	5: [("a", 4), ("b", 4)],
# }, {2}) 





assert not simple_state_machine.match("abb")
assert simple_state_machine.match("aab")
assert simple_state_machine.match("aababab")


class HalfLanguage(StateMachine):

	def __init__(self, full_language, full_accept_states, antecedents_graph):
		self.full_language = full_language
		self.full_accept_states = frozenset(full_accept_states)
		self.antecedents_graph = antecedents_graph
	
	def initial_state(self):
		return (self.full_language.initial_state(), self.full_accept_states)

	def accept(self, state):
		(full_state, antecedents_states) = state
		return full_state in antecedents_states

	def transitions(self, state):
		(full_state, antecedents_states) = state
		for (tlet, dest) in self.full_state.transitions():
			new_antecedents = set()
			for antecedents_state in antecedents_states:
				new_antecedents |= self.antecedents_graph[antecedents_state]
			yield (tlet, (dest, frozenset(new_antecedents)))


def make_half_language(state_machine):
	antecedents = defaultdict(set)
	accepting = set()
	visited = {state_machine.initial_state()}
	to_visit = []
	while to_visit:
		state = to_visit.pop()
		if state.accept:
			accepting.add(state)
		successors = [state.default] + [dest for (_, dest) in state.transitions]
		antecedents[dest].add(tlet)
		if dest not in visited:
			visited.add(dest)
			to_visit.append(dest)
	antecedents = {
		key: frozenset(value)
		for (key,value) in antecedents
	}
	return HalfLanguage(state_machine, accepting, antecedents)


half_language = make_half_language(simple_state_machine)
assert not simple_state_machine.match("abb")
assert simple_state_machine.match("aab")