dictionary comparison

[pzs at dcs.gla.ac.uk]

he final version is below. I had to tweak it slightly since my
transitions are labelled, and I also had to deal with transitions which
were repeated within a single state. The code is much faster than my
quick-and-dirty implementation, and now performs a provably optimal
minimization, since it mimics the Hopcroft-Ullman algorithm only in a
more data-structure friendly way.

Unfortunately I haven't found my target application minimizes very much
at all, especially after an application of the subset construction. This
algorithm only really works well in densely linked systems, which
unfortunately I don't have. Still, it was an interesting programming
exercise, and one in which I think Python proved its mettle...

Thanks a lot for your help - you saved me from a quagmire of nesting and
the resulting debugging nightmare...

Peter


while 1:
		keys = FSA.keys()

		# find out which states are equivalent and
		# can thus be simplified down to one
		removedict = {}
		for istate1 in range(len(keys)-1):
        		state1 = keys[istate1]
        		if removedict.has_key(state1): continue
        		for istate2 in range(istate1+1, len(keys)):
           			state2 = keys[istate2]
           			if FSA[state1] == FSA[state2]:
					removedict[state2] = state1

		# exit when no more simplifications can
		# be performed (no equivalent states)
		if not removedict.keys(): break

		# apply the simplifications
		newFSA = {}
		for state in keys:
        		# don't reproduce states to be simplified
        		if removedict.has_key(state): continue
        		transitions = []
        		for dest in FSA[state]:
				if removedict.has_key(dest[1]):
					dest = [dest[0], removedict[dest[1]]]

				# don't reproduce transitions within a state
				if dest in transitions:
					continue
				else:
					transitions.append(dest)
        		newFSA[state] = transitions

		FSA = newFSA


Sent via Deja.com http://www.deja.com/
Before you buy.