大学の試験で「与えられた言語を認識するような状態数最小の有限オートマトンを答える」問題が頻出されているため, 検算用のプログラムを書いてみます.
NFA の入力形式
input.txt として以下のように与えます.
2 0 0,0 1,0, 1,2,2, 2,3,3, 3,,,1
一行目は[入力文字の種類数] [始状態] を空白区切りで与えています.
二行目以降はCSVのようになっていて, カンマ区切りのうち, 最初の要素は状態の番号づけ, 二番目から最後から二番目までの要素は各文字を読み取ったあとの状態遷移, 最後の要素は「その状態が終状態か否か」を示します. 状態遷移に関しては, NFAなので, 状態が複数ある場合は空白区切りで列挙し, 一つもない場合は空文字になります. 終状態か否かに関しては, 終状態の場合のみ何かしら文字を入れることにします.
状態数最小のDFA に変換するプログラム
間違いがあれば指摘してほしいです. 私のテストの成績が上がるかもしれないので... gist: https://gist.github.com/7ma7X/bf42cc4b3f251e88c9bc55b5eb34eb3b
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)
例
にある「10110を部分語として含むような言語」でやってみます. NFA で書くと
なので, input.txt は
2 0 0,0,0 1, 1,2,, 2,,3, 3,,4, 4,5,, 5,5,5,1
となります. プログラムを実行してみます.
pprint.pprint(nfa) をアンコメントすると,
[{'0': '0', '1': '2', '2': '', '3': '', '4': '5', '5': '5'},
{'0': '0 1', '1': '', '2': '3', '3': '4', '4': '', '5': '5'},
{'0': False, '1': False, '2': False, '3': False, '4': False, '5': True}]
これは, 一つ目の連想配列が0に関して読む前をkey, 読んだ後をvalueとしていて, 二つ目の連想配列が1に関して読む前をkey, 読んだ後をvalueとしていて, 最後が終状態か否か, を表しています.
ラベルを張り替える前の pprint.pprint(dfa) をアンコメントすると,
[{'0': '0',
'0 1': '0 2',
'0 1 3': '0 2',
'0 1 3 5': '0 2 5',
'0 1 4': '0 2 5',
'0 1 4 5': '0 2 5',
'0 1 5': '0 2 5',
'0 2': '0',
'0 2 5': '0 5',
'0 5': '0 5'},
{'0': '0 1',
'0 1': '0 1',
'0 1 3': '0 1 4',
'0 1 3 5': '0 1 4 5',
'0 1 4': '0 1',
'0 1 4 5': '0 1 5',
'0 1 5': '0 1 5',
'0 2': '0 1 3',
'0 2 5': '0 1 3 5',
'0 5': '0 1 5'},
{'0': False,
'0 1': False,
'0 1 3': False,
'0 1 3 5': True,
'0 1 4': False,
'0 1 4 5': True,
'0 1 5': True,
'0 2': False,
'0 2 5': True,
'0 5': True}]
状態数が10個にまで広がってしまっていますね. ラベルを貼りかえた後の pprint.pprint(dfa) をアンコメントすると,
[{0: 0, 1: 7, 2: 7, 3: 8, 4: 8, 5: 8, 6: 8, 7: 0, 8: 9, 9: 9},
{0: 1, 1: 1, 2: 4, 3: 5, 4: 1, 5: 6, 6: 6, 7: 2, 8: 3, 9: 6},
{0: False,
1: False,
2: False,
3: True,
4: False,
5: True,
6: True,
7: False,
8: True,
9: True}]
と, だいぶ見やすくなりました. そして最終結果は
始状態: 1
[{0: 0, 1: 1, 2: 5, 3: 5, 4: 0, 5: 1},
{0: 0, 1: 2, 2: 2, 3: 4, 4: 2, 5: 3},
{0: True, 1: False, 2: False, 3: False, 4: False, 5: False}]
と, 状態数6個になります. これを整理して図示すると,
まあ多分合ってるんじゃないかと思います.
ここおかしいんじゃね？みたいなところがあったら是非是非コメントしてください.