編譯原理實(shí)驗(yàn)nfa確定化為dfa-展示頁(yè)
2025-07-08 16:57本頁(yè)面
【正文】 一條a弧而到達(dá)的狀態(tài)的全體。 輸入 根據(jù)課本NFA的定義，輸入五元組，依次輸入狀態(tài)集、輸入符號(hào)、初態(tài)集、終態(tài)集以及映像，將這些分別存入五個(gè)列表中。 closure算法 定義closure函數(shù)形式為closure(a,f)，其中，a為要做closure閉包的狀態(tài)集合，f為NFA的映像的集合。設(shè)立一個(gè)空列表s，用于存放每次closure閉包新加入的狀態(tài)。 ，即判斷f中狀態(tài)一等于a中狀態(tài)的弧，再判斷f中該狀態(tài)的弧是否為ε（具體代碼中用’$’代替），若是，則將該弧的狀態(tài)二加入s中。若s不為空，說(shuō)明本次循環(huán)仍然有新增狀態(tài)，則將新增狀態(tài)加入b中，并且將新增的狀態(tài)集合賦值給a，以新增的狀態(tài)集繼續(xù)做循環(huán)判斷，直到某次循環(huán)s為空結(jié)束。move算法只需要求從狀態(tài)集合中某一狀態(tài)經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)全體，所以不需要進(jìn)行while循環(huán)執(zhí)行多次，只需執(zhí)行closure算法中c步驟一次即可。具體思想為： ，存于C1中，C2的第一個(gè)元素賦值為0。 ，直到C2中所有元素為1，表示標(biāo)記完畢，執(zhí)行完成，所得到C1為最終狀態(tài)子集。五、實(shí)驗(yàn)小結(jié) 本次實(shí)驗(yàn)主要遇到了以下問(wèn)題： 輸入存儲(chǔ)問(wèn)題 若根據(jù)課本形式應(yīng)輸入M=(K,E,f,S,Z)，再對(duì)f進(jìn)行展開(kāi)，雖然用算法實(shí)現(xiàn)這一形式不難，但是對(duì)于后續(xù)的操作不太方便，所以最終選擇了依次輸出五元組，分別存于五個(gè)列表中。 輸出問(wèn)題 輸出的形式最終沒(méi)有實(shí)現(xiàn)DFA的狀態(tài)圖而是使用矩陣的形式輸出，問(wèn)題在于對(duì)于以狀態(tài)集合為結(jié)點(diǎn)構(gòu)造狀態(tài)圖這樣的圖形形式方面的知識(shí)不了解，最終以矩陣形式輸出。六、附件源代碼K = [] 狀態(tài)E = [] 符號(hào)f = [] 弧S = [] 初態(tài)Z = [] 終態(tài) 輸入print(39。)a = input(39。)K = (39。)a = input(39。)E = (39。)a = input(39。)S = (39。)a = input(39。)Z = (39。)print(39。)n = int(input())print(39。)for i in range(n): ([]) a = input() f[len(f
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1