1、編譯原理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱 不確定有限狀態(tài)自動(dòng)機(jī)的確定化 實(shí)驗(yàn)時(shí)間 院系 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級(jí) 學(xué)號(hào) 姓名 1.試驗(yàn)?zāi)康妮斎耄?非確定有限（窮）狀態(tài)自動(dòng)機(jī)。輸出： 確定化的有限（窮）狀態(tài)自動(dòng)機(jī)2.實(shí)驗(yàn)原理一個(gè)確定的有限自動(dòng)機(jī)（DFA）M可以定義為一個(gè)五元組，M（K，F(xiàn)，S，Z），其中：（1） K是一個(gè)有窮非空集，集合中的每個(gè)元素稱為一個(gè)狀態(tài)；（2） 是一個(gè)有窮字母表，中的每個(gè)元素稱為一個(gè)輸入符號(hào)；（3） F是一個(gè)從K×K的單值轉(zhuǎn)換函數(shù)，即F（R，a）Q，（R，QK）表示當(dāng)前狀態(tài)為R，如果輸入字符a，則轉(zhuǎn)到狀態(tài)Q，狀態(tài)Q稱為狀態(tài)R的后繼狀態(tài)；（4） SK，是惟一的初態(tài)；（5） ZK

2、，是一個(gè)終態(tài)集。由定義可見(jiàn)，確定有限自動(dòng)機(jī)只有惟一的一個(gè)初態(tài)，但可以有多個(gè)終態(tài)，每個(gè)狀態(tài)對(duì)字母表中的任一輸入符號(hào)，最多只有一個(gè)后繼狀態(tài)。 對(duì)于DFA M，若存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，則稱這條通路上的所有弧的標(biāo)記符連接形成的字符串可為DFA M所接受。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則稱可為M所接受（或識(shí)別），DFA M所能接受的全部字符串（字）組成的集合記作L（M）。 一個(gè)不確定有限自動(dòng)機(jī)（NFA）M可以定義為一個(gè)五元組，M（K，F(xiàn)，S，Z），其中：（1） k是一個(gè)有窮非空集，集合中的每個(gè)元素稱為一個(gè)狀態(tài)；（2） 是一個(gè)有窮字母表，中的每個(gè)元素稱為一個(gè)輸入符號(hào)；（3） F是

3、一個(gè)從K×K的子集的轉(zhuǎn)換函數(shù)；（4） SK，是一個(gè)非空的初態(tài)集；（5） ZK，是一個(gè)終態(tài)集。由定義可見(jiàn)，不確定有限自動(dòng)機(jī)NFA與確定有限自動(dòng)機(jī)DFA的主要區(qū)別是：（1）NFA的初始狀態(tài)S為一個(gè)狀態(tài)集，即允許有多個(gè)初始狀態(tài)；（2）NFA中允許狀態(tài)在某輸出邊上有相同的符號(hào)，即對(duì)同一個(gè)輸入符號(hào)可以有多個(gè)后繼狀態(tài)。即DFA中的F是單值函數(shù)，而NFA中的F是多值函數(shù)。因此，可以將確定有限自動(dòng)機(jī)DFA看作是不確定有限自動(dòng)機(jī)NFA的特例。和DFA一樣，NFA也可以用矩陣和狀態(tài)轉(zhuǎn)換圖來(lái)表示。對(duì)于NFA M，若存在一條從某個(gè)初態(tài)結(jié)點(diǎn)到某一個(gè)終態(tài)結(jié)點(diǎn)的通路，則稱這條通路上的所有弧的標(biāo)記（除外）連接形成的

4、字符串可為M所接受。NFA M所能接受的全部字符串（字）組成的集合記作L（M）。由于DFA是NFA的特例，所以能被DFA所接受的符號(hào)串必能被NFA所接受。設(shè)M1和M2是同一個(gè)字母集上的有限自動(dòng)機(jī)，若L（M1）L（M2），則稱有限自動(dòng)機(jī)M1和M2等價(jià)。由以上定義可知，若兩個(gè)自動(dòng)機(jī)能夠接受相同的語(yǔ)言，則稱這兩個(gè)自動(dòng)機(jī)等價(jià)。DFA是NFA的特例，因此對(duì)于每一個(gè)NFA M1總存在一個(gè)DFA M2，使得L（M1）L（M2）。即一個(gè)不確定有限自動(dòng)機(jī)能接受的語(yǔ)言總可以找到一個(gè)等價(jià)的確定有限自動(dòng)機(jī)來(lái)接受該語(yǔ)言。NFA確定化為DFA同一個(gè)字符串可以由多條通路產(chǎn)生，而在實(shí)際應(yīng)用中，作為描述控制過(guò)程的自動(dòng)機(jī)，通常都

5、是確定有限自動(dòng)機(jī)DFA，因此這就需要將不確定有限自動(dòng)機(jī)轉(zhuǎn)換成等價(jià)的確定有限自動(dòng)機(jī)，這個(gè)過(guò)程稱為不確定有限自動(dòng)機(jī)的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1） 若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號(hào)用來(lái)表示若干個(gè)狀態(tài)構(gòu)成的某一狀態(tài)。（2） 設(shè)DFA的狀態(tài)集K中有一狀態(tài)為Si，Si+1，Sj，若對(duì)某符號(hào)a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 則令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 為DFA的一個(gè)轉(zhuǎn)換函數(shù)。若 Si，Si+1，Sk 不在K中，則將

6、其作為新的狀態(tài)加入到K中。（3） 重復(fù)第2步，直到K中不再有新的狀態(tài)加入為止。（4） 上面得到的所有狀態(tài)構(gòu)成DFA的狀態(tài)集K，轉(zhuǎn)換函數(shù)構(gòu)成DFA的F，DFA的字母表仍然是NFA的字母表。（5） DFA中凡是含有NFA終態(tài)的狀態(tài)都是DFA的終態(tài)。對(duì)于上述NFA確定化算法子集法，還可以采用另一種操作性更強(qiáng)的描述方式，下面我們給出其詳細(xì)描述。首先給出兩個(gè)相關(guān)定義。 假設(shè)I是NFA M狀態(tài)集K的一個(gè)子集（即IK），則定義-closure（I）為：（1） 若QI，則Q-closure（I）；（2） 若QI，則從Q出發(fā)經(jīng)過(guò)任意條弧而能到達(dá)的任何狀態(tài)Q，則Q-closure（I）。狀態(tài)集-closure（I

7、）稱為狀態(tài)I的閉包。假設(shè)NFA M（K，F(xiàn)，S，Z），若IK，a，則定義Ia-closure（J），其中J是所有從-closure（I）出發(fā)，經(jīng)過(guò)一條a弧而到達(dá)的狀態(tài)集。NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個(gè)狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動(dòng)機(jī)確定化。經(jīng)過(guò)確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)就需要簡(jiǎn)化。3.實(shí)驗(yàn)內(nèi)容（1）根據(jù)實(shí)驗(yàn)原理，編寫對(duì)應(yīng)的算法，并用合適的數(shù)據(jù)結(jié)構(gòu)加以實(shí)現(xiàn)（2）根據(jù)算法內(nèi)容，編寫源代碼，并進(jìn)行仔細(xì)的調(diào)試（3）調(diào)試無(wú)誤后，輸入相應(yīng)的實(shí)驗(yàn)數(shù)據(jù)對(duì)程序進(jìn)行檢測(cè)4.實(shí)驗(yàn)心得實(shí)驗(yàn)讓我更加深入得了解什么是NFA和DFA，隨

8、著實(shí)驗(yàn)次數(shù)的增多，現(xiàn)在做起實(shí)驗(yàn)來(lái)更加順暢了5.實(shí)驗(yàn)代碼與結(jié)果#include "stdafx.h"#include <stdio.h>#include <conio.h>/宏定義#define MAX_NODE 50/允許最多的結(jié)點(diǎn)數(shù)#define MAX_END 10/允許最多的輸入符號(hào)數(shù)#define MAX_DEGR 8/每個(gè)結(jié)點(diǎn)允許的最大出度#define MAX_TAB 200/狀態(tài)轉(zhuǎn)化矩陣最多行數(shù)#define BEGIN_STATE0/初始狀態(tài)結(jié)點(diǎn) int型#define END_STATE -1/終結(jié)狀態(tài)結(jié)點(diǎn) int型#define

9、EMPTY '#'/空代價(jià) char型#define AREA(n,from,to) (n) >= (from) && (n) <= (to) /判斷n是否在區(qū)間from,to/集合結(jié)構(gòu)體typedef struct musterint memberMAX_NODE;/集合的元素，最多為結(jié)點(diǎn)個(gè)數(shù)int num;/集合的元素個(gè)數(shù)muster;/函數(shù)聲明void musInit(muster* a);/初始化a集合void init(void);/初始化函數(shù)，將集合等清零void getData(void);/獲得用戶輸入數(shù)據(jù)void getDataEx

10、pert(void);/獲得用戶輸入數(shù)據(jù) 專家模式void taxis(muster* a);/排序函數(shù)，把集合里的元素按小到大排序bool isEqual(muster* a, muster* b);/判斷集合a與b是否相等 注意：判斷的兩個(gè)集合應(yīng)該已排序void eCLOSURE(muster*a, muster* b); /求a的空字閉包，結(jié)果保存到bvoid empty(int a, muster* b);/遞歸求結(jié)點(diǎn)a出發(fā)花費(fèi)空字到達(dá)的結(jié)點(diǎn)集合void aCLOSURE(muster*a, muster* b, char c);/求a經(jīng)過(guò)一條c弧到達(dá)的狀態(tài)結(jié)點(diǎn)全體的空字閉包，結(jié)果保存

11、到bint findLocal(int a);/找到結(jié)點(diǎn)表示為a的元素在node數(shù)組的下標(biāo)void addMem2Mus(muster* a, int b);/將b加至集合avoid addMus2Mus(muster* a, muster*b);/將集合b加至集合avoid printMus(muster*a);/打印a集合/為了便于處理，這里把一系列變量設(shè)置為全局變量int nodeNum;/結(jié)點(diǎn)數(shù)int endNum;/終結(jié)符數(shù)char endMAX_END;/終結(jié)符int nodeMAX_NODEMAX_DEGR+12;/nodei00保存結(jié)點(diǎn)的表示 -2表示開(kāi)始 -1表示終結(jié)/nod

12、ei01存當(dāng)前結(jié)點(diǎn)的出度n/nodei10-nodein+10保存當(dāng)前結(jié)點(diǎn)到下一結(jié)點(diǎn)的表示/nodei11-nodein+11 保存字符 當(dāng)前結(jié)點(diǎn)到下一結(jié)點(diǎn)的代價(jià)muster tabMAX_TABMAX_END + 1;/狀態(tài)轉(zhuǎn)化矩陣 其元素均為集合類型muster/END 全局變量void musInit(muster* a)/初始化a集合a->num = 0;void init()/初始化函數(shù)，將集合等清零int i,j;for(i=0; i<MAX_TAB; +i)for(j=0; j < MAX_END+1; +j)musInit(&tabij);void g

13、etData()/獲得用戶輸入數(shù)據(jù)int i, j, k;/循環(huán)輔助變量bool flg;/在判斷輸入代價(jià)是否合法時(shí)用的一個(gè)標(biāo)記/獲得合法的終結(jié)符數(shù)dofflush(stdin);/防止非數(shù)字的輸入導(dǎo)致死循環(huán) 不規(guī)范的用法 不推薦printf("nn請(qǐng)輸入輸入符號(hào)表的輸入符號(hào)總數(shù)(1,%d): ", MAX_END);scanf("%d", &endNum);while( !AREA(endNum, 1, MAX_END) );/獲得終結(jié)符集合for(i=0; i<endNum; +i)fflush(stdin);printf("

14、t輸入第 %d 個(gè)輸入符號(hào): ", i+1);scanf("%c", &endi);printf("n=nn");/獲得合法的結(jié)點(diǎn)總數(shù)dofflush(stdin);/防止非數(shù)字的輸入導(dǎo)致死循環(huán) 不規(guī)范的用法 不推薦printf("輸入結(jié)點(diǎn)總數(shù)包括開(kāi)始和結(jié)束結(jié)點(diǎn)(1,%d): ", MAX_NODE);scanf("%d", &nodeNum);while( !AREA(nodeNum, 1, MAX_NODE) );/獲得各個(gè)結(jié)點(diǎn)的相關(guān)數(shù)據(jù)for(i=0; i<nodeNum; +

15、i)fflush(stdin);printf("n輸入第%d個(gè)結(jié)點(diǎn)的代號(hào)只允許數(shù)字表示結(jié)點(diǎn)，且規(guī)定%d為初態(tài)X %d為終態(tài)Y: ", i+1, BEGIN_STATE, END_STATE);scanf("%d", &nodei00);if(END_STATE = nodei00)/如果當(dāng)前結(jié)點(diǎn)是終結(jié)符則不要去要求輸入當(dāng)前結(jié)點(diǎn)的其他數(shù)據(jù)nodei01 = 0;elsedofflush(stdin);printf("t輸入這個(gè)結(jié)點(diǎn)的出度即有多少條從這個(gè)結(jié)點(diǎn)出發(fā)的弧(0,%d): ", MAX_DEGR);scanf("

16、%d", &nodei01);while( !AREA(nodei01, 0, MAX_DEGR) );for(j=1; j <= nodei01; +j)fflush(stdin);printf("ntt輸入當(dāng)前結(jié)點(diǎn)的第 %d 條出發(fā)弧所到達(dá)的結(jié)點(diǎn): ", j);scanf("%d", &nodeij0);fflush(stdin);flg = true;/獲得一個(gè)有意義的代價(jià)符號(hào)即：代價(jià)只可能是空或者開(kāi)始時(shí)輸入的終結(jié)符集合中的一種doprintf("tt輸入當(dāng)前結(jié)點(diǎn)的第 %d 條出發(fā)弧所花費(fèi)的代價(jià)空弧用%c表

17、示: ", j, EMPTY);fflush(stdin);scanf("%c", &nodeij1);if(nodeij1 = EMPTY)flg = false;for(k=0; k<endNum; +k)if(nodeij1 = endk)flg = false;while(flg);void getDataExpert()/獲得用戶輸入數(shù)據(jù) int i, j;/循環(huán)輔助變量/獲得終結(jié)符數(shù)printf("nn輸入數(shù)據(jù)數(shù)據(jù)間用 一個(gè) 空格隔開(kāi):n");scanf("%d", &endNum);/獲得

18、終結(jié)符集合for(i=0; i<endNum; +i)getchar();scanf("%c", &endi);/獲得合法的結(jié)點(diǎn)總數(shù)scanf("%d", &nodeNum);/獲得各個(gè)結(jié)點(diǎn)的相關(guān)數(shù)據(jù)for(i=0; i<nodeNum; +i)scanf("%d", &nodei00);if(END_STATE = nodei00)/如果當(dāng)前結(jié)點(diǎn)是終結(jié)符則不要去要求輸入當(dāng)前結(jié)點(diǎn)的其他數(shù)據(jù)nodei01 = 0;elsescanf("%d", &nodei01);for(

19、j=1; j <= nodei01; +j)scanf("%d", &nodeij0);getchar();/獲得一個(gè)有意義的代價(jià)符號(hào)scanf("%c", &nodeij1);void taxis(muster* a)/排序函數(shù)，把集合里的元素按小到大排序int i, j;/循環(huán)輔助int temp;/臨時(shí)變量交換值/簡(jiǎn)單的冒泡排序 for(i=1; i < a->num; +i)for(j=0; j < i; +j)if(a->memberj > a->memberi)temp = a->

20、;memberi;a->memberi = a->memberj;a->memberj = temp;bool isEqual(muster* a, muster* b)/判斷集合a與b是否相等 注意：判斷的兩個(gè)集合應(yīng)該已排序int i;if(a->num != b->num)/元素個(gè)數(shù)不相等則集合不相等return false;for(i=0; i < a->num; +i)if(a->memberi != b->memberi)return false;return true;void eCLOSURE(muster*a, muster

21、* b) /求a集合的空字閉包，結(jié)果保存到bint i;muster tmp;musInit(&tmp);addMus2Mus(b, a);/集合a本身是屬于a的空字閉包for(i=0; i<a->num; +i)/分別求出a集合的每個(gè)元素的空字閉包保存到bempty(a->memberi, &tmp);addMus2Mus(b, &tmp);void aCLOSURE(muster*a, muster* b, char c) /求a經(jīng)過(guò)一條c弧到達(dá)的狀態(tài)結(jié)點(diǎn)全體的空字閉包/結(jié)果保存到bint xb;int i, j;muster tmp;musIni

22、t(&tmp);/求a經(jīng)過(guò)一條c弧到達(dá)的狀態(tài)結(jié)點(diǎn)全體 保存在tmp集合for(i=0; i<a->num; +i)xb = findLocal(a->memberi);/找到結(jié)點(diǎn)表示為a->memberi的元素在node數(shù)組的下標(biāo)/遍歷a->memberi結(jié)點(diǎn)的所有出度f(wàn)or(j=1; j <= nodexb01; +j)if(c = nodexbj1)/到下一結(jié)點(diǎn)代價(jià)為c則保存下一結(jié)點(diǎn)到集合addMem2Mus(&tmp, nodexbj0);/再求tmp集合的空字閉包 結(jié)果保存在集合beCLOSURE(&tmp,b);void e

23、mpty(int a, muster* b)/遞歸求結(jié)點(diǎn)a出發(fā)花費(fèi)空字到達(dá)的結(jié)點(diǎn)集合int xb;int i;if(a = END_STATE)/當(dāng)前結(jié)點(diǎn)是終點(diǎn)則不再往下找return;xb = findLocal(a);/找到結(jié)點(diǎn)表示為a的元素在node數(shù)組的下標(biāo)/遍歷a結(jié)點(diǎn)的所有出度f(wàn)or(i=1; i <= nodexb01; +i)if(nodexbi1 = EMPTY)/到下一結(jié)點(diǎn)空代價(jià)addMem2Mus(b, nodexbi0);/將下一結(jié)點(diǎn)保存到集合empty(nodexbi0, b);/遞歸過(guò)程int findLocal(int a)/找到結(jié)點(diǎn)表示為a的元素在node數(shù)

24、組的下標(biāo)int i;for(i=0; i<nodeNum; +i)if(a = nodei00)return i;printf("na錯(cuò)誤！無(wú)法在結(jié)點(diǎn)集合中找到標(biāo)記為 %d 的結(jié)點(diǎn)，請(qǐng)檢查你的輸入!nn", a);return -1;void addMem2Mus(muster* a, int b)/將b加至集合aint i;for(i=0; i<a->num; +i)if(b = a->memberi)break;/只有當(dāng)前集合中沒(méi)有b元素才將b加入if(i >= a->num)a->membera->num+ = b;ta

25、xis(a);/排序void addMus2Mus(muster* a, muster*b)/將集合b加至集合aint i;for(i=0; i<b->num; +i)addMem2Mus(a, b->memberi);void printMus(muster*a)/打印a集合int i;if(0 = a->num)/空集合printf(" - ");return;printf("");for(i=0; i<a->num; +i)switch(a->memberi)case BEGIN_STATE:printf(

26、"X");break;case END_STATE:printf("Y");break;default:printf("%d", a->memberi);(i = a->num - 1) ? printf("") : printf(" , ");/入口函數(shù)int main()int i, j, k;int searchx, searchy, lastx, lasty; muster tmp;musInit(&tmp);init();/獲取輸入數(shù)據(jù)printf(" N

27、FA轉(zhuǎn)DFA算法實(shí)現(xiàn)nn請(qǐng)按回車鍵后照提示操作：");if(getch() = ' ')getDataExpert();elsegetData();/子集法生成狀態(tài)轉(zhuǎn)化矩陣/處理轉(zhuǎn)化矩陣第一行empty(BEGIN_STATE, &tmp);/從開(kāi)始符開(kāi)始addMem2Mus(&tmp, BEGIN_STATE);/包括開(kāi)始符本身addMus2Mus(&tab00, &tmp);for(j=1; j<endNum+1; +j)/矩陣每行有endNum+1個(gè)集合aCLOSURE(&tab00, &tab0j, end

28、j-1);searchx = 0; searchy = 1;lastx = 0; lasty = endNum;/處理轉(zhuǎn)換矩陣的其他行for(i=1; ; +i)/至于矩陣有多少行，是要?jiǎng)討B(tài)決定的if(i >= MAX_TAB)printf("nta狀態(tài)轉(zhuǎn)化矩陣越界，請(qǐng)修改狀態(tài)轉(zhuǎn)化矩陣的最大行數(shù)宏nn");break;lastx = i-1;/確定Ifor(; searchx <= lastx; +searchx)if(searchy > endNum)/這個(gè)判斷非常重要searchy = 1;for(; searchy <= lasty; +sea

29、rchy)/判斷tabsearchxsearchy是否要插入第一列for(k=0; k <= lastx; +k)if (isEqual(&tabsearchxsearchy, &tabk0)break;/如果沒(méi)有重復(fù)的而且當(dāng)前集合非空則要把tabsearchxsearchy插入當(dāng)前行的第一列if(tabsearchxsearchy.num !=0 && k > lastx)addMus2Mus(&tabi0, &tabsearchxsearchy);goto endsearch;/這里必須用goto跳轉(zhuǎn)到多曾循環(huán)外/雖然goto的使用大有爭(zhēng)論但是這里采用其不會(huì)對(duì)程序的理解和維護(hù)帶來(lái)麻煩/else如果有重復(fù)的或者是空則我們轉(zhuǎn)到下一個(gè)集合判斷/當(dāng)所有的集合都判斷完了 則我們的轉(zhuǎn)化過(guò)程也完成了if(searchx > lastx)break;endsearch:/確定Ia Ib .for(j=1; j<endNum+1; +j)/矩陣每行有endNum+1個(gè)集合aCLOSURE(&tabi0, &tabij, endj-1);printf("通過(guò)子集法求得的狀態(tài)轉(zhuǎn)換矩陣為:n It&quo