NFA -> DFA & DFA minimization

nfa_to_min_dfa.py

import pprint

nfa = []

with open("input.txt", "r") as f:

    # アルファベットの種類数と始状態を読み取る
    n, nfa_initial_state = f.readline().split()
    n = int(n)
    for i in range(n+1):
        nfa.append(dict())

    for line in f.readlines():
        data = line.replace("\n", "").split(",")

        # 遷移を読み取る
        for i in range(n):
            nfa[i][data[0]] = data[i+1]

        # 終状態か否かを読み取る
        nfa[n][data[0]] = True if data[n+1] else False

# NFAを確認したい場合はここをアンコメント
# pprint.pprint(nfa)


# NFA -> DFA

dfa = []
for i in range(n+1):
    dfa.append(dict())

unchecked_states = [nfa_initial_state]
checked_states = []

while unchecked_states:
    tmp_states = unchecked_states.pop()
    checked_states.append(tmp_states)

    for i in range(n):
        # 終状態か否かを書き込む
        dfa[n][tmp_states] = False
        for el in tmp_states.split():
            if nfa[n][el]:
                dfa[n][tmp_states] = True
                break

        # 遷移を書き込む
        new_states = set()

        for el in tmp_states.split():
            if nfa[i][el]:
                next_list = nfa[i][el].split(" ")
                new_states = new_states.union(next_list)

        new_states = " ".join(sorted(list(new_states)))
        dfa[i][tmp_states] = new_states

        if new_states not in checked_states:
            unchecked_states.append(new_states)

# ラベル貼りかえ前のDFAを確認したい場合はここをアンコメント
# pprint.pprint(dfa)

# 状態のラベルの張り替え
checked_states = sorted(list(set(checked_states)))
m = len(checked_states)

for i in range(n+1):
    for j, state in enumerate(checked_states):
        if i == n:
            dfa[i][j] = dfa[i].pop(state)
        else:
            dfa[i][j] = checked_states.index(dfa[i].pop(state))

dfa_initial_state = checked_states.index(nfa_initial_state)
checked_states = list(range(m))

# ラベル貼りかえ後のDFAを確認したい場合はここをアンコメント
# pprint.pprint(dfa)


# DFAの最小化

min_dfa = []
for i in range(n+1):
    min_dfa.append(dict())

marked_list = []
unmarked_list = []

for i in range(m-1):
    for j in range(i+1, m):
        if (dfa[n][i] and not dfa[n][j]) or (not dfa[n][i] and dfa[n][j]):
            marked_list.append((i, j))
        else:
            unmarked_list.append((i, j))

while True:
    is_renewed = False

    for i in range(m-1):
        for j in range(i+1, m):
            for k in range(n):
                if dfa[k][i] < dfa[k][j]:
                    next_tuple = (dfa[k][i], dfa[k][j])
                else:
                    next_tuple = (dfa[k][j], dfa[k][i])

                if (i, j) in unmarked_list and next_tuple in marked_list:
                    is_renewed = True
                    unmarked_list.remove((i, j))
                    marked_list.append((i, j))

    if not is_renewed:
        break

# MarkedList, UnmarkedListを確認したい場合はここをアンコメント
# print(marked_list)
# print(unmarked_list)

state_num = 0

min_dfa_hash = dict()
for (i, j) in unmarked_list:
    if i in min_dfa_hash and j in min_dfa_hash:
        k = min_dfa_hash[i]
        l = min_dfa_hash[j]
        for state in checked_states:
            if state in min_dfa_hash and min_dfa_hash[state] == l:
                min_dfa_hash[state] = k
    elif i in min_dfa_hash:
        min_dfa_hash[j] = min_dfa_hash[i]
    elif j in min_dfa_hash:
        min_dfa_hash[i] = min_dfa_hash[j]
    else:
        min_dfa_hash[i] = min_dfa_hash[j] = state_num
        state_num += 1

for state in checked_states:
    if state not in min_dfa_hash:
        min_dfa_hash[state] = state_num
        state_num += 1

min_dfa_initial_state = min_dfa_hash[dfa_initial_state]
new_checked_states = []

for state in checked_states:
    tmp_state = min_dfa_hash[state]

    # 終状態か否かを書き込む
    if tmp_state in min_dfa[n] and not min_dfa[n][tmp_state]:
        if dfa[n][state]:
            min_dfa[n][tmp_state] = True
    elif tmp_state not in min_dfa[n]:
        if dfa[n][state]:
            min_dfa[n][tmp_state] = True
        else:
            min_dfa[n][tmp_state] = False

    # 遷移を書き込む
    if tmp_state in new_checked_states:
        continue
    else:
        new_checked_states.append(tmp_state)

        for i in range(n):
            min_dfa[i][tmp_state] = min_dfa_hash[dfa[i][state]]

new_checked_states = sorted(list(set(new_checked_states)))

for i in range(n+1):
    for j, state in enumerate(new_checked_states):
        if i == n:
            min_dfa[i][j] = min_dfa[i].pop(state)
        else:
            min_dfa[i][j] = new_checked_states.index(min_dfa[i].pop(state))

min_dfa_initial_state = checked_states.index(min_dfa_initial_state)

print("始状態: {}".format(min_dfa_initial_state))
pprint.pprint(min_dfa)