Convert a nondeterministic finite state automaton to a deterministic finite state automaton

non_deterministic_automata_convertor.py

"""Convert a nondeterministic finite state automaton to a deterministic finite state automaton"""

from collections import OrderedDict

START = 'a'
STATES = {
	'a': {
		0: {'a'},
		1: {'a', 'b'}
	},
	'b': {
		0: {'c'},
		1: {'c'}
	},
	'c': {
		0: set(),
		1: set()
	}
}


def where_you_can_go(states):
	possiblities = {0: set(), 1: set()}
	for state in states:
		you_can_go = STATES[state]
		for key, value in you_can_go.items():
			possiblities[key] = possiblities[key].union(value)
	return possiblities

memory = OrderedDict()
queue = [{START}]
while queue:
	last = frozenset(queue.pop(0))
	if last not in memory:
		possibilities = where_you_can_go(last)
		memory[last] = possibilities
		queue.extend(possibilities.values())

def pretty_please(setti):
	if len(setti) == 1:
		return str(next(iter(setti)))
	else:
		return "{%s}" % ', '.join(setti)


for key, value in memory.items():
	print "%s\t%s\t%s" % (
		pretty_please(key),
		pretty_please(value[0]),
		pretty_please(value[1])
	)