1、2016.11.02不確定有窮狀態(tài)自動機的確定化目錄一、實驗名稱2二、實驗目的2三、實驗原理21、NFA定義22、DFA的定義23、closure函數(shù)24、move函數(shù)3四、實驗思路31、輸入32、closure算法33、move算法34、構造子集45、輸出4五、實驗小結41、輸入存儲問題42、closure算法問題43、輸出問題5六、附件51、源代碼52、運行結果截圖7一、實驗名稱不確定有窮狀態(tài)自動機的確定化二、實驗目的輸入：非確定有窮狀態(tài)自動機NFA 輸出：確定化的有窮狀態(tài)自動機DFA三、實驗原理1、NFA定義一個不確定的有窮自動機M是一個五元組，M=(K,E,f,S,Z)其中a. K是一

2、個有窮集，它的每個元素稱為一個狀態(tài)；b. E是一個有窮字母表，它的每個元素稱為一個輸入符號；c. f是一個從KE*到K的子集的映像，即：K*E*-2k，其中2k表示K的冪集；d. S包含于K，是一個非空初態(tài)集；e. Z包含于K，是一個終態(tài)集。2、DFA的定義一個確定的有窮自動機M是一個五元組，M=(K,E,f,S,Z)其中a. K是一個有窮集，它的每個元素稱為一個狀態(tài)；b. E是一個有窮字母表，它的每個元素稱為一個輸入符號；c. f是轉換函數(shù)，是KE-K上的映像，即，如f(ki,a)=kj(kiK,kjK)就意味著，當前狀態(tài)為ki，輸入字符為a時，將轉換到下一狀態(tài)kj，我們把kj稱作ki的一個

3、后繼狀態(tài)；d. SK，是唯一的一個初態(tài)；e. Z包含于K，是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結束狀態(tài)。3、closure函數(shù)狀態(tài)集合I的閉包，表示為closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達的狀態(tài)的集合。4、move函數(shù)狀態(tài)集合I的a弧轉換，表示為move(I,a)，定義為狀態(tài)集合J，其中J是所有那些從I中的某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)的全體。四、實驗思路本次實驗采用python完成。1、輸入根據(jù)課本NFA的定義，輸入五元組，依次輸入狀態(tài)集、輸入符號、初態(tài)集、終態(tài)集以及映像，將這些分別存入五個列表中。其中關于映像的輸入格式：先輸入狀態(tài)一，再輸入輸入符號

4、，最后輸入狀態(tài)二，一次輸入一條弧。2、closure算法定義closure函數(shù)形式為closure(a,f)，其中，a為要做closure閉包的狀態(tài)集合，f為NFA的映像的集合。具體思想為：a.設立一個最終返回結果的列表b，初值與列表a相等。設立一個空列表s，用于存放每次closure閉包新加入的狀態(tài)。b.執(zhí)行while循環(huán)，此循環(huán)判斷條件為1，即會一直執(zhí)行下去，直到遇到closure閉包沒有新增狀態(tài)的時候執(zhí)行結束。c.對a中的每一個狀態(tài)求closure閉包，即判斷f中狀態(tài)一等于a中狀態(tài)的弧，再判斷f中該狀態(tài)的弧是否為（具體代碼中用$代替），若是，則將該弧的狀態(tài)二加入s中。d.判斷s是否為空，

5、若為空則說明此次循環(huán)沒有新增狀態(tài)，即說明closure閉包在上一次循環(huán)時已執(zhí)行完畢，輸出上次循環(huán)的結果b。若s不為空，說明本次循環(huán)仍然有新增狀態(tài)，則將新增狀態(tài)加入b中，并且將新增的狀態(tài)集合賦值給a，以新增的狀態(tài)集繼續(xù)做循環(huán)判斷，直到某次循環(huán)s為空結束。3、move算法move算法的核心思想與closure算法一致，其函數(shù)形式為move(a,e,f)，其中e為move算法move(I,a)的a。move算法只需要求從狀態(tài)集合中某一狀態(tài)經(jīng)過一條a弧而到達的狀態(tài)全體，所以不需要進行while循環(huán)執(zhí)行多次，只需執(zhí)行closure算法中c步驟一次即可。4、構造子集建立兩個列表C1、C2，其中C1用于存放

6、最終的狀態(tài)集，C2作為標記使用，對應C1中的子集，若C1中的子集也進行了closure閉包則C2中相應元素標記為1，否則為0。具體思想為：a.首先對初態(tài)集進行closure閉包，存于C1中，C2的第一個元素賦值為0。b.標記C2第一個元素為1，對C1中第一個集合先做move算法再做closure算法，若其中一個算法得出空集合則直接返回空列表，否則判斷C1中是否有該狀態(tài)集，若無則加入C1中，C2中相應元素賦值為0，表示未標記。c.重復執(zhí)行b步驟，直到C2中所有元素為1，表示標記完畢，執(zhí)行完成，所得到C1為最終狀態(tài)子集。5、輸出采用矩陣形式輸出，C1中每個狀態(tài)集合的下標為最終合并后的狀態(tài)。五、實驗

7、小結本次實驗主要遇到了以下問題：1、輸入存儲問題若根據(jù)課本形式應輸入M=(K,E,f,S,Z)，再對f進行展開，雖然用算法實現(xiàn)這一形式不難，但是對于后續(xù)的操作不太方便，所以最終選擇了依次輸出五元組，分別存于五個列表中。2、closure算法問題最初想用遞歸的思想實現(xiàn)closure算法，即每次進行一步closure閉包，返回結果為新得到的狀態(tài)集的closure閉包，但是對于遞歸結束的判斷條件以及參數(shù)的傳遞不太明確，所以最終沒有選擇遞歸，而是選擇了死循環(huán)里面加上退出循環(huán)條件的形式完成。3、輸出問題輸出的形式最終沒有實現(xiàn)DFA的狀態(tài)圖而是使用矩陣的形式輸出，問題在于對于以狀態(tài)集合為結點構造狀態(tài)圖這樣

8、的圖形形式方面的知識不了解，最終以矩陣形式輸出。通過本次實驗，對于NFA轉換為DFA的過程有了深刻的認識，對于closure算法和move算法的思想非常清楚。六、附件1、源代碼K = # 狀態(tài)E = # 符號f = # 弧S = # 初態(tài)Z = # 終態(tài)# 輸入print(E21414020 陳國柱)a = input(輸入狀態(tài)(以空格區(qū)分,以換行結束):)K = a.split( )a = input(輸入輸入符號(以空格區(qū)分,以換行結束):)E = a.split( )a = input(輸入初態(tài)(以空格區(qū)分,以換行結束):)S = a.split( )a = input(輸入終態(tài)(以空格

9、區(qū)分,以換行結束):)Z = a.split( )print(輸入弧的條數(shù):)n = int(input()print(輸入弧(分別輸入狀態(tài)1,輸入符號,狀態(tài)2,以空格區(qū)分換行結束,表示為$)for i in range(n): f.append() a = input() flen(f)-1 = a.split( )# closure 算法def closure(a, f): # a為列表 b = a while 1: s = for i in a: for j in range(len(f): if i = fj0 and fj1 = $: s.append(fj2) if len(s)

10、= 0: break else: for i in s: b.append(i) a = s return sorted(b)# move 算法def move(a, e, f): # a為列表 e為一個符號 s = for i in a: for j in range(len(f): if i = fj0 and fj1 = e: s.append(fj2) return sorted(s)# 算出最終子集C1 = # C1為最終子集C2 = C1.append(closure(S, f)C2.append(0)while C2.pop(len(C2)-1) = 0: C2.append(0

11、) for i in range(len(C1): if C2i = 0: C2i = 1 for j in E: A = move(C1i, j, f) if A = : break B = closure(A, f) if B = : break k = 0 for m in C1: if B = m: k = k+1 if k = 0: C1.append(B) C2.append(0)print(輸出NFA構造的子集:)print(C1)print(輸出DFA:)print(S, end= )for x in E: print(x, end= )print(n)# 輸出DFAfor i in range(len(C1): print(i, end= ) for j in E: a1 = move(C1i, j, f) if a1 = : print(a1, end= ) continue a2 = closure(a1, f) if a2 = : print(