編譯原理實(shí)驗(yàn)DFA最小化

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

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

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

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

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

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

7、原本定義中的列表類型都轉(zhuǎn)為集合類型，最后輸出。同時(shí)定義中的f需要單獨(dú)輸出。六、附件1、源代碼K = # 狀態(tài)E = # 符號(hào)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 陳國(guó)柱) print(輸入DFA M) M = input(以定義形式輸入DFA(如:M=(K,E,f,S,Z):) N = M.split() for i in N: zanshi1.append(i.split()

8、 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(,) for i in Z1: Z.append(i) print(輸入f中弧的條數(shù):) n = int(input() print(輸入弧(分別輸入狀態(tài)1,輸入符號(hào),狀態(tài)2,以空格區(qū)分換行

9、結(jié)束,表示為$) for i in range(n): f.append() a = input() flen(f)-1 = a.split( )def move(a, e, f): # a為列表 e為一個(gè)符號(hào) s = for i in a: for j in range(len(f): if i = fj0 and fj1 = e: 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 l

10、en(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(ziji1).difference(set(KKk) != 0: flag = flag+1 if flag = len(KK): glag = glag + 1 break if glag = 1: ilag = jj zhenziji1 = zhenziji1.a

11、ppend(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): zz = zz.append(zijij) ziji1 = move(zz, Eilag, f) if len(set(ziji1).difference(set(KKhlag) = 0: zhenziji1.append(zijij) else: zhenz

12、iji2.append(zijij) KK.pop(i) KK.append(zhenziji1) KK.append(zhenziji2) else: llag = llag+1 if llag = len(KK): break# 運(yùn)行putin()operation()for yy in KK: if len(yy) = 2: 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