編譯原理課程設(shè)計(jì)--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實(shí)現(xiàn)-其他專業(yè)-文庫(kù)吧資料
2025-01-27 02:55本頁(yè)面
【正文】 （ 2）陳火旺 .程序設(shè)計(jì)語(yǔ)言編譯原理 .2021 年 1 月第 3 版 . 北京 :國(guó)防工業(yè)出版社 . （ 3） 嚴(yán)蔚敏、吳偉民 .數(shù) 據(jù)結(jié)構(gòu)（ C 語(yǔ)言版） .1997 年 4 月第 1版 .北京 :清華大學(xué)出版社 .2021 （ 4） 王曉東編著 .計(jì)算機(jī)算法設(shè)計(jì)與分析 .電子工業(yè)出版社 .2021 第 13 頁(yè)，共 22 頁(yè) 8. 附錄 NFA 轉(zhuǎn)換為 DFA 采用 C++編程實(shí)現(xiàn)代碼如下 includeiostream includestring define MAXS 100 using namespace std。編譯原理是一門實(shí)用性很強(qiáng)，對(duì)我們的專業(yè)很有幫助的科目 ,我將會(huì)繼續(xù)努力 ,不斷增加自己的知識(shí)面 ,把編譯原理學(xué)習(xí)的更好。經(jīng)過(guò)這次課程設(shè)計(jì) ,也讓我深刻的認(rèn)識(shí)到實(shí)踐才是最重要的。很好的理解了子集法的演算過(guò)程。運(yùn)行結(jié)果因?yàn)檗D(zhuǎn)換字符輸入順序的不同，得出的結(jié)果有可能與筆算得出的順序有所不同，但是結(jié)果依然是正確。對(duì)于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號(hào)前的是新?tīng)顟B(tài)名，冒號(hào)后的是舊狀態(tài)名。 I Ia Ib {x,5,1} {5,1,3} {5,1,4} {5,1,3} {5,1,3,2,6,y} {5,1,4} {5,1,4} {5,1,3} {5,1,4,2,6,y} {5,1,3,2,6,y} {5,1,3,2,6,y} {5,1,4,6,y} {5,1,4,2,6,y} {5,1,3,6,y} {5,1,4,2,6,y} {5,1,4,6,y} {5,1,3,6,y} {5,1,4,2,6,y} {5,1,3,6,y} {5,1,3,2,6,y} {5,1,4,6,y} X 5 3 4 6 2 1 9 Y a b b a ε ε ε ε a b a b 第 8 頁(yè)，共 22 頁(yè) 步驟 2： 在上表中將原 NFA初態(tài)的ε 閉包作為轉(zhuǎn)換后的 DFA 的初態(tài)，包含原 NFA終態(tài)的狀態(tài)作為轉(zhuǎn)換后的 DFA 的終態(tài)，并進(jìn)行重新編號(hào)得到轉(zhuǎn)換后的 DFA的狀態(tài)轉(zhuǎn)移矩陣如下： a b {x,5,1} 1 {5,1,3} 2 {5,1,4} 3 {5,1,3} 2 {5,1,3,2,6,y}4 {5,1,4} 3 {5,1,4} 3 {5,1,3}2 {5,1,4,2,6,y} 5 {5,1,3,2,6,y} 4 {5,1,3,2,6,y}4 {5,1,4, 6,y} 6 {5,1,4,2,6,y} 5 {5,1,3, 6,y} 7 {5,1,4,2,6,y} 5 {5,1,4, 6,y} 6 {5,1,3, 6,y} 7 {5,1,4,2,6,y} 5 {5,1,3, 6,y} 7 {5,1,3,2,6,y} 4 {5,1,4, 6,y} 6 步驟 3： 畫出轉(zhuǎn)換后的 DFA 的狀態(tài)圖： 1 2 3 7 6 5 4 5 a b b a a a b b a b a a b b 0 0 0 1 1 1 1 第 9 頁(yè)，共 22 頁(yè) 4 程序?qū)崿F(xiàn) 程序框架圖 數(shù)據(jù)流程圖 NFA 轉(zhuǎn)化為DFA NFA圖結(jié)構(gòu) NFA狀態(tài)表 DFA圖結(jié)構(gòu) 初始化狀態(tài)轉(zhuǎn)換矩陣 狀態(tài)轉(zhuǎn)換操作 第 10 頁(yè)，共 22 頁(yè) 實(shí)現(xiàn)代碼 （見(jiàn)附錄） 運(yùn)行環(huán)境 （ 1）開(kāi)發(fā)平臺(tái)： Microsoft visual C++ （ 2）運(yùn)行平臺(tái)： Windows xp/Windows 2021 程序?qū)崿F(xiàn)結(jié)果 實(shí)現(xiàn) NFA 例題為： NFA M=({S,P,Z},{0,1},f,{s,p},{z}) 開(kāi)始 NFA 消除空轉(zhuǎn)移 子集構(gòu)造法 NFA狀態(tài)矩陣 DFA 狀態(tài)圖 第 11 頁(yè)，共 22 頁(yè) 其中 f(s,0)={p} f(z,0)={p} f(p,1)={z} f(z,1)={p} f(s,1)={s,z} 根據(jù)例題輸入 NFA 各邊的信息 得出結(jié)果如下圖 ： 第 12 頁(yè)，共 22 頁(yè) 本程序應(yīng)在 Microsoft Visual C++ 下運(yùn)行。 步驟 1： 以 I， Ia、 Ib 等為列做表，其中 I列第一行的內(nèi)容是初態(tài)的ε 閉包所得到的狀態(tài)集合。用數(shù)學(xué)表達(dá)就是 {p|p 屬于 εclosure(t) , t屬于 T} move(T,a) NFA的集合，這個(gè)集合在 input symbol 為 a，狀態(tài)為 T中任意狀態(tài)情況下，通過(guò)一個(gè)轉(zhuǎn)換得到的集合 例如： 對(duì)于以下?tīng)顟B(tài)圖中： ε closure({0})={0,1,2,4,7} 在這里設(shè) I={0,1,2,4,7}，則 因?yàn)橛?move(I,a)={3,8}=J,所以 Ia= ε closure(J)= ε closure({3,8})={1,2,3,4,6,7,8} 0 1 2 3 5 7 6 8 9 4 9 100 ε ε 第 7 頁(yè)，共 22 頁(yè) 子集構(gòu)造法 確定化每個(gè) 多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù) ,具體轉(zhuǎn)換，采用子集構(gòu)造法?？梢詫懽鳎? Ia= ε closure(J)， J=move(I,a),其中， J是從 I 中任一狀態(tài)出發(fā)經(jīng)過(guò)一條 a 弧到達(dá)的狀態(tài)集合，記為 move(I,a)。 .消除 N?? 形式的產(chǎn)生式，即消除空轉(zhuǎn)移 。 轉(zhuǎn)換思路 由非確定的有限自動(dòng)機(jī)出發(fā)構(gòu)造與之等價(jià)的確定的有限自動(dòng)機(jī)的辦法是確定的有限自動(dòng)機(jī)的狀態(tài)對(duì)應(yīng)于非確定的有限自動(dòng)機(jī)的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA 的每一個(gè)狀態(tài)對(duì)應(yīng) NFA 的一組狀態(tài)。 第 2 頁(yè)，共 22 頁(yè) 和 DFA 的概念 不確定有限自動(dòng)機(jī) NFA NFA(nondeterministic finitestate automata)即非確定有限自動(dòng)機(jī) , 一個(gè)非確定的有限自動(dòng)機(jī) NFA M’是一個(gè)五元式 : NFA M’ =(S, Σ∪ {ε }, δ , S0, F) 其中 S— 有限狀態(tài)集，Σ∪ {ε }— 輸入符號(hào)加上ε ,即自動(dòng)機(jī)的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1