DFA Minimizer (partial)

dfamin.py

# States
Q = frozenset('abcdef')
# Alphabet (input symbols)
Sigma = frozenset([0, 1])
# Transition Function (Q x Sigma -> Q)
delta = {
  ('a', 0): 'b',
  ('a', 1): 'c',
  ('b', 0): 'a',
  ('b', 1): 'd',
  ('c', 0): 'e',
  ('c', 1): 'f',
  ('d', 0): 'e',
  ('d', 1): 'f',
  ('e', 0): 'e',
  ('e', 1): 'f',
  ('f', 0): 'f',
  ('f', 1): 'f',
}
# Initial State (element of Q)
q0 = 'a'
# Accept States (subset of Q)
F = frozenset('cde')

# Hopcroft's algorithm
P = {F, Q - F}
W = {F}
while W:
  A = W.pop()
  for c in Sigma:
    X = frozenset(state for state in Q if delta[state, c] in A)
    loop = True
    while loop:
      loop = False
      for Y in P:
        if (X & Y) and (Y - X):
          P.remove(Y)
          P |= {X & Y, Y - X}
          if Y in W:
            W.remove(Y)
            W |= {X & Y, Y - X}
          else:
            if len(X & Y) <= len(Y - X):
              W.add(X & Y)
            else:
              W.add(Y - X)
          loop = True
          break

# Print output
print("List of new states from old states:")
for i, old_states in enumerate(sorted(map(list, P))):
  print(
    "new state {0} <- old state(s) {1}".format(
    i,
    ', '.join(
      sorted(
        map(str,
          old_states)))))

stdout.txt

List of new states from old states:
new state 0 <- old state(s) a, b
new state 1 <- old state(s) c, d, e
new state 2 <- old state(s) f