Skip to content

Instantly share code, notes, and snippets.

@kaisugi
Last active January 12, 2019 17:22
Show Gist options
  • Save kaisugi/bf42cc4b3f251e88c9bc55b5eb34eb3b to your computer and use it in GitHub Desktop.
Save kaisugi/bf42cc4b3f251e88c9bc55b5eb34eb3b to your computer and use it in GitHub Desktop.
NFA -> DFA & DFA minimization
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment