NFA到DFA轉(zhuǎn)化

1、目錄1.需求分析21.2 NFA和DFA之間的聯(lián)系32.概要設(shè)計(jì)33.詳細(xì)設(shè)計(jì)43.1 子集構(gòu)造法43.2 具體轉(zhuǎn)換過程63.3 程序設(shè)計(jì)93.3.1 常量定義93.3.2 數(shù)據(jù)結(jié)構(gòu)定義93.3.3 主要函數(shù)流程圖114.測(cè)試分析145.用戶手冊(cè)166.課程總結(jié)161.需求分析1.1 NFA和DFA的概念NFA(nondeterministic finite-state automata)即非確定有限自動(dòng)機(jī), 一個(gè)非確定的有限自動(dòng)機(jī)NFA M是一個(gè)五元式: NFA M=(S, , , S0, F)其中 S有限狀態(tài)集 輸入符號(hào)加上,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以是中一個(gè)字符或是. S0初態(tài)集

2、F終態(tài)集 轉(zhuǎn)換函數(shù) S× 2S (2S -S的冪集S的子集構(gòu)成的集合）DFA(deterministic finite-state automata)即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī)DFA M是一個(gè)五元式: M=(S, ，, S0, Z) 其中: S 有限狀態(tài)集 輸入字母表 映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù)) S×S (s,a)=S , S, S S, a S0 初始狀態(tài) S0 S Z終止?fàn)顟B(tài)集 ZÍS1.2 NFA和DFA之間的聯(lián)系在非確定的有限自動(dòng)機(jī)NFA中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個(gè)可能的后續(xù)狀態(tài)中進(jìn)行選擇，故一個(gè)NFA對(duì)符號(hào)串的識(shí)別就必然是一個(gè)試探的過程

3、。這種不確定性給識(shí)別過程帶來的反復(fù)，無疑會(huì)影響到FA的工作效率。而DFA則是確定的,將NFA轉(zhuǎn)化為DFA將大大提高工作效率,因此將NFA轉(zhuǎn)化為DFA是有其一定必要的。2.概要設(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 程序總框圖3.詳細(xì)設(shè)計(jì)3.1 子集構(gòu)造法已證明：非確定的有限自動(dòng)機(jī)與確定的有限自動(dòng)機(jī)從功能上來說是等價(jià)的，也就是說，我們能夠從：NFA M D

4、FA M使得 L(M)=L(M)為了使得NFA確定化，我們首先給出兩個(gè)定義：定義1:集合I的-閉包：令I(lǐng)是一個(gè)狀態(tài)集的子集，定義-closure（I）為：1）若sI，則s-closure（I）；2）若sI，則從s出發(fā)經(jīng)過任意條弧能夠到達(dá)的任何 狀態(tài)都屬于-closure（I）。 狀態(tài)集-closure（I）稱為I的-閉包定義2:令I(lǐng)是NFA M的狀態(tài)集的一個(gè)子集, a 定義: Ia=-closure(J) 其中J = (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

5、:bbaab0123 4圖2與之等價(jià)的DFA如圖3：bab0，12，443a圖33.2 具體轉(zhuǎn)換過程為了說明跟清晰，我們使用實(shí)例說明，構(gòu)造正規(guī)式101（0|1）*011的DFA？解：首先構(gòu)造相應(yīng)的NFA，如圖4所示：10111001012356478圖4將其寫成M五元式則為：M=(0，1，2，3，4，5，6，7，8，0，1,，0，8)其中為： （0，1）1 （1，0）2 （2，1）3 （3，）4 （4，）5 （4，0）4 （4，1）4 （5，0）6 （6，1）7 （7，1）8 它所對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣如表1：表1狀態(tài)010112233444455667788根據(jù)NFA轉(zhuǎn)化為DFA的子集法轉(zhuǎn)換法進(jìn)

6、行轉(zhuǎn)換，對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣見表2：表2II0I1011223，4，53，4，54，5，64，54，5，64，5，64，5，74，54，5，64，54，5，74，5，64，5，84，5，84，5，64，5對(duì)上表重新命名后的狀態(tài)轉(zhuǎn)換矩陣見表3：表3II0I1011223345446545647745將其寫成M五元式則為：M=(0，1，2，3，4，5，6，7，0，1，0，5)其中為： （0，1）1 （1，0）2 （2，1）3 （3，0）4 （3，1）5 （4，0）4 （4，1）6 （5，0）4 （5，1）5 （6，0）4 （6，1）7 （7，0）4 （7，1）5 與表3對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換圖如圖5所示：1

7、10001101101236745圖5這樣就完成了從正規(guī)表達(dá)式101（0|1）*011到DFA的轉(zhuǎn)化。3.3 程序設(shè)計(jì)3.3.1 常量定義#define MAX 10#define NumMaxChar 10#define NumMAXTN 10 #define INFINIT 327673.3.2 數(shù)據(jù)結(jié)構(gòu)定義NFA圖結(jié)構(gòu)定義如下：typedef struct edge /邊int dest;char cost;struct edge *link; /指向下一邊*Edge; typedef struct vertex /頂點(diǎn)char data; /狀態(tài)Edge adj; /邊*Vertex;

8、 typedef struct graph /圖Vertex NodeTable;int NumVertex;int MaxNumVertex;int NumEdge;*Graph;狀態(tài)轉(zhuǎn)換表機(jī)構(gòu)定義如下：typedef struct tablenode /轉(zhuǎn)換表節(jié)點(diǎn)char newname; /新命名char chMAX; /頂點(diǎn)集合*TableNode; typedef struct tablequeue /轉(zhuǎn)換表列TableNode TNMAX; /轉(zhuǎn)換表節(jié)點(diǎn)數(shù)組char transword; /轉(zhuǎn)換條件int NumTn; /添加的頂點(diǎn)數(shù)*TableQueue; typedef str

9、uct transmatrix /狀態(tài)轉(zhuǎn)換矩陣TableQueue TQ; /轉(zhuǎn)換表列組int transnum; /轉(zhuǎn)換表列數(shù)*TranMatrix;3.3.3 主要函數(shù)流程圖void Smove函數(shù)流程圖如圖6所示：00非0非00非0開始int i,j,k=0,check,len;Edge p;while(t2k!='0')k+;for(i=0;i<MAX;i+)for(j=0;j<g->NumVertex;j+)if(g->NodeTablej.data=t1i) p=g->NodeTablej.adj;while(p!=NULL)if(p-

10、>cost=transword) check=CheckChar(t2,g->NodeTablep->dest.data);if(check=1) t2k=g->NodeTablep->dest.data;k+;p=p->link;elsep=p->link;len=k；BubbleSort(t2,k);結(jié)束圖6void Show_TranMatrix函數(shù)流程圖如圖7所示：000非0非0非0開始int i,j,k;printf("狀態(tài)轉(zhuǎn)換矩陣:n");for(j=0;j<=TM->transnum;j+)printf(&

11、quot;轉(zhuǎn)換字符:%c ",TM->TQj.transword);printf("n");for(k=0;k<MAX;k+)for(j=0;j<=TM->transnum;j+)if(TM->TQj.TNk->newname='0') printf("NULL ");else printf("%c:",TM->TQj.TNk->newname);for(i=0;TM->TQj.TNk->chi!='0'i+) printf(&quo

12、t;%c",TM->TQj.TNk->chi);if(TM->TQj.TNk->ch0='0') printf("NULL");printf(" "); 結(jié)束printf("n");圖74.測(cè)試分析用正規(guī)表達(dá)式101（0|1）*011進(jìn)行測(cè)試。首先在“請(qǐng)輸入NFA的總狀態(tài)數(shù)”后輸入“9”，接著在“請(qǐng)依次輸入NFA的狀態(tài)名稱:”后依次輸入08，在“請(qǐng)輸入NFA的邊數(shù):”后輸入“10”，然后依次輸入各起始狀態(tài)、接受字符和到達(dá)狀態(tài)，接受字符為2，依次為0、1，新狀態(tài)依次命名為07，程序最后結(jié)果正確。程序運(yùn)行截圖如下：5.用戶手冊(cè) 本程序應(yīng)在Microsoft Visual C+ 6.0下運(yùn)行。NFA的確定化是編譯過程