Минимизатор DFA в python - PullRequest
Новая
       14

Минимизатор DFA в python

1 голос
/ 19 апреля 2020

Я создаю минимизатор DFA, используя python, и я застрял. Я использую алгоритм, который нашел в Интернете, но он не дает мне правильного результата, и я не могу понять, почему. 

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)

По сути, я пытаюсь распечатать все неразличимые состояния в конце. Правильный результат (для примера, который я использую): 

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

, и результат, который я получаю: 

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

Как видите, все текущие в но есть некоторые дополнительные, которые не должны быть здесь. Проходя через код, я понимаю, почему это происходит, но я не уверен, как это исправить. Любые идеи?

1 Ответ

1 голос
/ 19 апреля 2020

Сначала я организовал входной DFA в более управляемую форму: 

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'}

Вот моя попытка реализовать алгоритм. При сравнении пар у меня возникли проблемы с определением порядка, поэтому я преобразовал все в frozenset s, а не в кортежи или списки. 

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'})}
...