編譯原理實驗DFA最小化

1、2016.11.09確定有窮自動機(jī)的最小化目錄一、實驗名稱2二、實驗?zāi)康?三、實驗原理21、DFA的定義22、無用狀態(tài)23、狀態(tài)等價條件2四、實驗思路31、輸入32、move算法33、子集劃分算法34、輸出4五、實驗小結(jié)41、輸入存儲問題42、子集劃分算法問題43、輸出問題4六、附件41、源代碼42、運行結(jié)果截圖7一、實驗名稱確定有窮自動機(jī)的最小化二、實驗?zāi)康?、輸入DFA，輸出等價的狀態(tài)數(shù)最少的DFA；2、實現(xiàn)子集劃分算法；3、輸入和輸出均以定義的形式。三、實驗原理1、DFA的定義一個確定的有窮自動機(jī)M是一個五元組，M=(K,E,f,S,Z)其中a. K是一個有窮集，它的每個元素稱為一個狀態(tài)

2、；b. E是一個有窮字母表，它的每個元素稱為一個輸入符號；c. f是轉(zhuǎn)換函數(shù)，是K×E->K上的映像，即，如f(ki,a)=kj(kiK,kjK)就意味著，當(dāng)前狀態(tài)為ki，輸入字符為a時，將轉(zhuǎn)換到下一狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；d. SK，是唯一的一個初態(tài)；e. Z包含于K，是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。2、無用狀態(tài)所謂有窮自動機(jī)的無用狀態(tài)，是指這樣的狀態(tài)：從該自動機(jī)的開始狀態(tài)出發(fā)，任何串也不能到達(dá)的那個狀態(tài)。或者從這個狀態(tài)沒有通路到達(dá)狀態(tài)。3、狀態(tài)等價條件a.一致性條件狀態(tài)s和t必須同時為可接受狀態(tài)或不可接受狀態(tài)b.蔓延性條件對于所有輸入符號，狀

3、態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價的狀態(tài)里。四、實驗思路本次實驗采用python完成。1、輸入根據(jù)實驗要求，以DFA的定義形式輸入，即輸入M=(K,E,f,S,Z)，其中f另外輸入。采用putin作為輸入函數(shù)，首先輸入定義形式，用split函數(shù)按照進(jìn)行分割，再按照分割。最后對得到的二維列表zanshi1中的元素進(jìn)行輸出，得到K,E,S,Z。再輸入f中弧的條數(shù)，依次輸入弧。2、move算法move算法與NFA的確定化里的算法一樣，在這里為了求某一子集經(jīng)過弧到達(dá)什么子集而使用move算法。思路是：建立一個新列表存放move算法產(chǎn)生的狀態(tài)集合，若f中的弧的輸入符號為a或者b，求經(jīng)過緊跟a或者b的下一個狀態(tài)，

4、將這些狀態(tài)放于新列表中。3、子集劃分算法定義operation()函數(shù)為子集劃分算法函數(shù)，具體執(zhí)行步驟如下：a.將K中的狀態(tài)集分為兩種：終態(tài)集和非終態(tài)集，存于KK中，KK存放最終劃分后得到的集合。b.設(shè)立循環(huán)條件，子集劃分算法劃分最細(xì)的情況是每個狀態(tài)都為一個子集，所以以此作為循環(huán)條件。若KK中集合個數(shù)不等于K中狀態(tài)個數(shù)，則繼續(xù)循環(huán)。c.設(shè)立標(biāo)志位llag=0用來決定是否跳出循環(huán)，每不執(zhí)行一次劃分算法則llag加1，若最終llag等于KK長度，說明此次循環(huán)沒有子集劃分，則說明劃分完畢，退出循環(huán)。d.對KK中的集合依次進(jìn)行操作，判斷他們進(jìn)過move算法得到的集合是否是KK中已有的集合，若是則不執(zhí)行

5、劃分，否則執(zhí)行劃分算法。e. 若執(zhí)行劃分算法，則先算出集合中首個狀態(tài)的move算法得到的集合屬于哪個已知集合，再對其他狀態(tài)進(jìn)行同樣操作，和首個狀態(tài)move算法屬于相同集合的放于同一個列表中，其他的放于另一個列表中。f.將KK中原來要劃分的集合刪除，加入劃分后的兩個集合。循環(huán)執(zhí)行上述步驟，知道KK中集合個數(shù)和標(biāo)志位llag值相同或者KK中集合個數(shù)等于K中狀態(tài)個數(shù)，則退出循環(huán)。4、輸出輸出同樣為DFA的定義形式，先輸出M=(K,E,f,S,Z)，再輸出其中的f。五、實驗小結(jié)本次實驗主要遇到了以下問題：1、輸入存儲問題輸入要求使用定義形式，需要區(qū)分輸入的元素，分別得到狀態(tài)集，輸入符號集，初態(tài)集以及終

6、態(tài)集。通過python中的split函數(shù)將輸入的字符串分別以和分開，再通過循環(huán)操作取出得到的二維列表中每一個元素的第二個元素，即為所求的狀態(tài)集，輸入符號集，初態(tài)集以及終態(tài)集，再輸出f的具體弧。2、子集劃分算法問題子集劃分算法需要對劃分后得到的集合一直執(zhí)行劃分算法，但是會有一個表示劃分完畢的結(jié)果，在程序中通過設(shè)立兩個條件來判斷是否劃分完畢，一是劃分得到的子集個數(shù)是否等于狀態(tài)集中狀態(tài)個數(shù)，若是則說明每個狀態(tài)都為一個子集，即肯定劃分結(jié)束。另一判斷條件為設(shè)置一個標(biāo)志位，通過觀察標(biāo)志位的數(shù)值來判斷本次劃分算法是否執(zhí)行，若沒有執(zhí)行則說明已經(jīng)劃分完畢，同樣退出循環(huán)。3、輸出問題輸出的形式為DFA的定義形式，

7、通過對格式的控制，將原本定義中的列表類型都轉(zhuǎn)為集合類型，最后輸出。同時定義中的f需要單獨輸出。六、附件1、源代碼K = # 狀態(tài)E = # 符號f = # 弧f1 = # 新弧S = # 初態(tài)Z = # 終態(tài)zanshi1 = # 存放五元組形式1KK = # 最終狀態(tài)集#M=(1,2,3,4,5,6,7,a,b,f,1,5,6,7)# 輸入def putin(): print('E21414020 陳國柱') print('輸入DFA M') M = input('以定義形式輸入DFA(如:M=(K,E,f,S,Z):') N = M.spli

8、t('') for i in N: zanshi1.append(i.split('') K1 = (zanshi101) K1 =K1.split(',') for i in K1: K.append(i) E1 = (zanshi111) E1 =E1.split(',') for i in E1: E.append(i) S1 = (zanshi121) S1 =S1.split(',') for i in S1: S.append(i) Z1 = (zanshi131) Z1 =Z1.split('

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

10、s.append(fj2) return sorted(s)# 子集劃分算法def operation(): a = for x in K: if x not in Z: a.append(x) KK.append(a) KK.append(Z) while len(KK) != len(K): llag = 0 for i in range(len(KK): ziji = KKi glag = 0 for jj in range(len(E): ziji1 = move(ziji, Ejj, f) flag = 0 for k in range(len(KK): if len(set(zij

11、i1).difference(set(KKk) != 0: flag = flag+1 if flag = len(KK): glag = glag + 1 break if glag = 1: ilag = jj zhenziji1 = zhenziji1.append(ziji0) ziji1 = move(zhenziji1, Eilag, f) for k in range(len(KK): if len(set(ziji1).difference(set(KKk) = 0: hlag = k break zhenziji2 = for j in range(1, len(ziji):

12、 zz = zz.append(zijij) ziji1 = move(zz, Eilag, f) if len(set(ziji1).difference(set(KKhlag) = 0: zhenziji1.append(zijij) else: zhenziji2.append(zijij) KK.pop(i) KK.append(zhenziji1) KK.append(zhenziji2) else: llag = llag+1 if llag = len(KK): break# 運行putin()operation()for yy in KK: if len(yy) >= 2

13、: for i in range(1, len(yy): if yyi in K: K.remove(yyi) if yyi in S: S.remove(yyi) if yyi in Z: Z.remove(yyi) for yyy in f: if yyy0 = yyi: yyy0 = yy0 if yyy2 = yyi: yyy2 = yy0for yy in f: if yy not in f1: f1.append(yy)for i in range(len(K): Ki = int(Ki)for i in range(len(S): Si = int(Si)for i in range(len(Z): Zi = int(Zi)print('輸出最小化DFA M')print('M1=(',set(K),',',set(E), ',', 'f', '