從NFA到DFA的轉(zhuǎn)化實(shí)驗(yàn)報(bào)告剖析

1、計(jì)算機(jī)理論基礎(chǔ)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目 ：從 NFA 到 DFA 的轉(zhuǎn)化 姓 名 ：院（系） ： 專業(yè)班級(jí) ： 學(xué) 號(hào) ： 指導(dǎo)教師 ：設(shè)計(jì)日期 ：2013 年 11月 1日一、實(shí)驗(yàn)?zāi)康模?. 了解NFA和DFA的概念2. NFA和DFA之間的聯(lián)系3. 從NFA到DFA的轉(zhuǎn)化程序編寫二、實(shí)驗(yàn)原理1. NFANFA( non determi nistic fin ite-state automata)即非確定有限自動(dòng)機(jī)，個(gè)非確定的有限自動(dòng)機(jī) NFA M是一個(gè)五元式：NFA M' =(S,藝 U £ , S , SO, F)其中S 有限狀態(tài)集工U £ 輸入符號(hào)加上£

2、,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以是 工中一個(gè)字符或是£ .S0 初態(tài)集F終態(tài)集轉(zhuǎn)換函數(shù)S X藝U £ 2S(2S -S 的幕集一S的子集構(gòu)成的集合)2. DFADFA(deterministicfinite-stateautomata)即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī)DFA M是一個(gè)五元式：M=(S, 藝，S , S0, Z)其中：S有限狀態(tài)集工一輸入字母表S 映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù))S d SS (s,a)=S ', S, S ' S, a 2S0初始狀態(tài)S0 SZ終止?fàn)顟B(tài)集Z S3. NFA和DFA之間的聯(lián)系在非確定的有限自動(dòng)機(jī)NFA中，由于

3、某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù) 狀態(tài)中進(jìn)行選擇，故一個(gè)NFA對(duì)符號(hào)串的識(shí)別就必然是一個(gè)試探的過程。 這種不 確定性給識(shí)別過程帶來的反復(fù)，無疑會(huì)影響到 FA的工作效率。而DFA則是確定 的,將NFA轉(zhuǎn)化為DFA將大大提高工作效率,因此將NFA?；癁镈FA是有其一定必 要的。三、實(shí)驗(yàn)設(shè)計(jì)通過本課程設(shè)計(jì)教學(xué)所要求達(dá)到的目的是：充分理解和掌握NFA DFA以及NFA確定化過程的相關(guān)概念和知識(shí)，理解和掌握子集法的相關(guān)知識(shí)和應(yīng)用，編程 實(shí)現(xiàn)對(duì)輸入NFA轉(zhuǎn)換成DFA俞出的功能。程序總框圖如圖1所示：NFA圖結(jié)構(gòu)狀態(tài)轉(zhuǎn)換表 機(jī)構(gòu)總控模塊圖操作初始化狀態(tài)轉(zhuǎn)換矩陣狀態(tài)轉(zhuǎn)換操 作圖1程序總框圖1、子集構(gòu)造法已證

4、明：非確定的有限自動(dòng)機(jī)與確定的有限自動(dòng)機(jī)從功能上來說是等價(jià)的， 也就是說，我們能夠從：NFA M' |DFA- M使得L(M)=L(M')為了使得NFA確定化，我們首先給出兩個(gè)定義：定義1:集合I的閉包：令I(lǐng)是一個(gè)狀態(tài)集的子集，定義£ -closure (I )為：1) 若 s I，則 s £ -closure (I);2) 若s I，則從s出發(fā)經(jīng)過任意條£弧能夠到達(dá)的任何狀態(tài)都屬于 £ -closure (I )。狀態(tài)集£ -closure (I)稱為I的£ -閉包定義2:令I(lǐng)是NFA M'的狀態(tài)集的一個(gè)子集

5、, a 2定義：Ia= £ -closure(J)其中 J = US (s,a)J是從狀態(tài)子集I中的每個(gè)狀態(tài)出發(fā)，經(jīng)過標(biāo)記為a的弧而達(dá)到的狀態(tài) 集合。Ia是狀態(tài)子集，其元素為J中的狀態(tài)，加上從J中每一個(gè)狀態(tài)出發(fā)通過 £弧到達(dá)的狀態(tài)。給定如圖2所示的NFA:與之等價(jià)的DFA如圖3:2、程序設(shè)計(jì)2.1常量定義#defi ne MAX 10#defi ne NumMaxChar 10#defi ne NumMAXTN 10#defi ne INFINIT 327672.2數(shù)據(jù)結(jié)構(gòu)定義NFA圖結(jié)構(gòu)定義如下：typedef struct edge /int dest;char cos

6、t;指向下一邊struct edge *li nk;/*Edge;頂點(diǎn) / 狀態(tài) 邊typedef struct vertex /char data;Edge adj; /*Vertex;typedef struct graph /Vertex NodeTable;int NumVertex;int MaxNumVertex;int NumEdge;*Graph; 狀態(tài)轉(zhuǎn)換表機(jī)構(gòu)定義如下： typedef struct tablenode /char newname; / char chMAX; / *TableNode;typedef struct tablequeue /TableNode

7、 TNMAX; / char transword; / int NumTn; / *TableQueue;typedef struct transmatrix /TableQueue TQ;/int transnum; /轉(zhuǎn)換表節(jié)點(diǎn) 新命名 頂點(diǎn)集合轉(zhuǎn)換表列 轉(zhuǎn)換表節(jié)點(diǎn)數(shù)組 轉(zhuǎn)換條件 添加的頂點(diǎn)數(shù)狀態(tài)轉(zhuǎn)換矩陣轉(zhuǎn)換表列組轉(zhuǎn)換表列數(shù)NFA的然后依新狀態(tài)*Tra nMatrix;3.測(cè)試分析用正規(guī)表達(dá)式101 (0|1 ) *011進(jìn)行測(cè)試。程序運(yùn)行截圖如下:首先在“請(qǐng)輸入NFA的總狀態(tài)數(shù)”后輸入“ 9”，接著在“請(qǐng)依次輸入 狀態(tài)名稱：”后依次輸入08,在“請(qǐng)輸入NFA的邊數(shù)：”后輸入“ 10”,

8、次輸入各起始狀態(tài)、接受字符和到達(dá)狀態(tài)，接受字符為 2,依次為0、1, 依次命名為07，程序最后結(jié)果正確。IULLNULLIULLNULLIIIN N 入1A1A1A1A1A1ALL-&H -&H -TT -&H名名名名名名名名 態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)態(tài)初始狀態(tài)轉(zhuǎn)換字符舊NULLNULL轉(zhuǎn)換字符沢HULLNULL:1：7NULLNULLNULLNULLNULL NULL NULL HULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULL NULLNULL NULL HULL NULL NULL NULL NULL NU

9、LL HULL NULL NULL HULL NULL NULL HULL NULL二二二二二二二二二二二轉(zhuǎn)換過程=I嗚 IH li丨 I h、L NJBI口、LI 幵flk 111IH1111n轉(zhuǎn)換字符旳NULL NULL 2:2NULL NULL4：4564:4564:4564：4564:456NULLNULL轉(zhuǎn)換字符：丄1：1HULL NULL3:3455沁56:45?5:45 7：45S 5:45NULL NULLNULL NULL NULL NULL轉(zhuǎn)化后的DFR為：<0,1,1><1,0.2> a丄a<3r0,4><3,lr5><4,0,4><4,1,6?<5,0,4><5,1,5?<7,0,4><7,1,55看序結(jié)東，銷毀圈- 圖己銷毀Press anv kev to cont inue四、實(shí)驗(yàn)總結(jié)通過此次對(duì)從NFA到DFA的轉(zhuǎn)化的設(shè)計(jì)，使我更好的理解了 NFA確定化過程 的相關(guān)知識(shí)，很好的理解了子集法的演算過程。 經(jīng)過多次試驗(yàn)， 在正確輸入相關(guān) 數(shù)據(jù)的情況下，程序能正常運(yùn)行， 當(dāng)錯(cuò)誤操作或輸入錯(cuò)誤數(shù)據(jù)時(shí)， 程序?qū)?yīng)錯(cuò)誤