編譯原理課程設(shè)計(jì)--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實(shí)現(xiàn)-其他專業(yè)(完整版)
【正文】 //NFA 邊數(shù) struct edge{ string first。經(jīng)過這次課程設(shè)計(jì) ,也讓我深刻的認(rèn)識(shí)到實(shí)踐才是最重要的。 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 頁，共 22 頁 步驟 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 頁，共 22 頁 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 頁，共 22 頁 實(shí)現(xiàn)代碼 （見附錄） 運(yùn)行環(huán)境 （ 1）開發(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}) 開始 NFA 消除空轉(zhuǎn)移 子集構(gòu)造法 NFA狀態(tài)矩陣 DFA 狀態(tài)圖 第 11 頁，共 22 頁 其中 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 頁，共 22 頁 本程序應(yīng)在 Microsoft Visual C++ 下運(yùn)行。 .消除 N?? 形式的產(chǎn)生式，即消除空轉(zhuǎn)移 。 deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA 目錄 ： ............................................................ 1 背景 ......................................................... 1 實(shí)踐目的 ..................................................... 1 課程實(shí)踐的意義 ............................................... 1 和 DFA 的概念 .................................................. 2 不確定有限自動(dòng)機(jī) NFA......................................... 2 確定有限自動(dòng)機(jī) DFA ........................................... 3 3．從 NDF 到 DFA的等價(jià)變化步驟 ...................................... 5 轉(zhuǎn)換思路 ..................................................... 5 .................................................. 5 子集構(gòu)造法 ................................................... 7 4程序?qū)崿F(xiàn) .......................................................... 9 程序框架圖 ................................................... 9 數(shù)據(jù)流程圖 .................................................. 9 實(shí)現(xiàn)代碼 .................................................... 10 運(yùn)行環(huán)境 .................................................... 10 程序?qū)崿F(xiàn)結(jié)果 ................................................ 10 ......................................................... 12 ： ....................................................... 12 考 文 獻(xiàn)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1