DFA minimizer in python

Question

I'm building a DFA minimizer using python and I'm stuck. I'm using an algorithm I found online but it doesn't give me the correct result and I can't figure out why.

functions = {'p1,c': 'p2', 'p1,d': 'p6', 'p2,c': 'p7', 'p2,d': 'p3', 'p3,c': 'p1', 'p3,d': 'p3', 'p4,c': 'p3', 
         'p4,d': 'p7', 'p5,c': 'p8', 'p5,d': 'p6', 'p6,c': 'p3', 'p6,d': 'p7', 'p7,c': 'p7', 'p7,d': 'p5',
         'p8,c': 'p7', 'p8,d': 'p3'}

DS = ['p1', 'p2', 'p3', 'p4', 'p5', 'p6', 'p7', 'p8']
acceptedStates = ['p3']
symbols = ['c', 'd']

# ---- some more code here that's currently not important ----

dist = []
for pair in pairs: #pairs is a list of lists with all possible pairs of states
    if (pair[0] in acceptableStates and par[1] not in prihvatljivaStanja) or (pair[0] not in acceptableStates and par[1] in acceptableStates):
        dist.append(pair)


for pair in pairs:
    for symbol in symbols:
        priv1 = functions[par[0] + ',' + symbol]
        priv2 = functions[par[1] + ',' + symbol]
        if (priv1 in acceptableStates and priv2 not in acceptableStates) or (priv1 not in acceptableStates and priv2 in acceptableStates):
            dist.append(pair)

for i in pairs:
    if i not in dist:
        print(i)

Basically what I'm trying to do is print out all indistinguishable states at the end. The correct result is (for the example I'm using) is:

dist = [['p1', 'p5'], ['p2', p8'], ['p4', 'p6']]

and the result I get is:

dist = [['p1', 'p5'] #correct
       ['p1', 'p7']
       ['p2', 'p8'] #correct
       ['p4', 'p6'] #correct
       ['p5', 'p7']]

As you can see, all the current ones are in the but it has some extra that shouldn't be here. While going through the code I can see why this happens, but I'm not sure how to fix it. Any ideas?

Answer 1

First I organized the input DFA into a more managable form:

dfa = {'p1': {'c': 'p2', 'd': 'p6'},
       'p2': {'c': 'p7', 'd': 'p3'},
       'p3': {'c': 'p1', 'd': 'p3'},
       'p4': {'c': 'p3', 'd': 'p7'},
       'p5': {'c': 'p8', 'd': 'p6'},
       'p6': {'c': 'p3', 'd': 'p7'},
       'p7': {'c': 'p7', 'd': 'p5'},
       'p8': {'c': 'p7', 'd': 'p3'}}

final = {'p3'}

Here's my attempt to implement the algorithm. I was running into problems with order mattering when comparing pairs, so I converted everything to frozensets, rather than tuples or lists.

from itertools import combinations

pairs = set(map(frozenset, combinations(dfa, 2)))
dist = set()

for pair in pairs:
    p, q = pair
    if (p in final and q not in final) or (p not in final and q in final):
        dist.add(pair)

repeat = True
while repeat:
    repeat = False
    for pair in pairs:
        print(dist)
        if pair in dist:
            continue
        p, q = pair
        for a in dfa[p]:
            dpair = frozenset((dfa[p].get(a), dfa[q].get(a)))
            if dpair in dist:
                dist.add(pair)
                repeat = True
                break

print(pairs - dist)
# {frozenset({'p1', 'p5'}), frozenset({'p8', 'p2'}), frozenset({'p6', 'p4'})}