不確定有窮自動(dòng)機(jī)的確定化

1、編譯原理實(shí)驗(yàn)報(bào)告不確定有限狀態(tài)自動(dòng)機(jī)的確定化實(shí)驗(yàn)名稱 2011/5/23實(shí)驗(yàn)時(shí)間 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)院系 08計(jì)算機(jī)一班班級(jí) E學(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è)從KK的單值轉(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

2、，是惟一的初態(tài)；（5） ZK，是一個(gè)終態(tài)集。由定義可見，確定有限自動(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è)元素稱為

3、一個(gè)輸入符號(hào)；（3） F是一個(gè)從KK的子集的轉(zhuǎn)換函數(shù)；（4） SK，是一個(gè)非空的初態(tài)集；（5） ZK，是一個(gè)終態(tài)集。由定義可見，不確定有限自動(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)換圖來表示。對(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ī)能夠接受相同的語言，則稱這兩個(gè)自動(dòng)機(jī)等價(jià)。DFA是NFA的特例，因此對(duì)于每一個(gè)NFA M1總存在一個(gè)DFA M2，使得L（M1）L（M2）。即一個(gè)不確定有限自動(dòng)機(jī)能接受的語言總可以找到一個(gè)等價(jià)的確定有限自動(dòng)機(jī)來接受該語言。NFA確定化為DFA同一個(gè)字符串可以由多條通路產(chǎn)生，而在實(shí)際應(yīng)用中，作為描述控制過程的

5、自動(dòng)機(jī)，通常都是確定有限自動(dòng)機(jī)DFA，因此這就需要將不確定有限自動(dòng)機(jī)轉(zhuǎn)換成等價(jià)的確定有限自動(dòng)機(jī)，這個(gè)過程稱為不確定有限自動(dòng)機(jī)的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1） 若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號(hào)用來表示若干個(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

6、不在K中，則將其作為新的狀態(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)過任意條弧而能到達(dá)的任何狀態(tài)Q，則Q-closure（I）。狀態(tài)集-cl

7、osure（I）稱為狀態(tài)I的閉包。假設(shè)NFA M（K，F(xiàn)，S，Z），若IK，a，則定義Ia-closure（J），其中J是所有從-closure（I）出發(fā)，經(jīng)過一條a弧而到達(dá)的狀態(tài)集。NFA確定化的實(shí)質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個(gè)狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動(dòng)機(jī)確定化。經(jīng)過確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價(jià)狀態(tài)，這時(shí)就需要簡(jiǎn)化。3. 實(shí)驗(yàn)內(nèi)容 實(shí)現(xiàn)計(jì)算閉包c(diǎn)losure（I）的算法； 實(shí)現(xiàn)轉(zhuǎn)換函數(shù)move（q，a）的算法； 輸出界面如下：NFA的 圖形形式DFA的圖形形式4. 實(shí)驗(yàn)心得本次實(shí)驗(yàn)對(duì)我來說是非常困難的，因?yàn)槲乙酝木幊探?jīng)驗(yàn)匱乏，

8、故滿腔墨水無從傾灑。所以，本次的實(shí)驗(yàn)代碼是我從網(wǎng)上下載得來的。雖然代碼不是我所寫，但我可以保證的是程序?qū)嵗俏覄?chuàng)建并自己手動(dòng)輸入的，對(duì)于程序的設(shè)計(jì)原理和運(yùn)行過程我還是相當(dāng)熟練的。針對(duì)于這種情況，我已決定以后加強(qiáng)鍛煉，逐步提升自己的編程能力，不僅要做到能讀得懂，也要能寫得出。但此非一朝一夕，希望老師能夠理解。5.實(shí)驗(yàn)代碼#define MAX 10#define INFINIT 32767#define NumMaxChar 10#define NumMAXTN 10 #include #include #include typedef struct edge/邊int dest;char co

9、st;struct edge *link;/指向下一邊*Edge; typedef struct vertex/頂點(diǎn)char data;/狀態(tài)Edge adj;/邊*Vertex; typedef struct graph/圖Vertex NodeTable;int NumVertex;int MaxNumVertex;int NumEdge;*Graph;typedef struct tablenode/轉(zhuǎn)換表節(jié)點(diǎn)char newname;/新命名char chMAX;/頂點(diǎn)集合*TableNode; typedef struct tablequeue/轉(zhuǎn)換表列TableNode TNMAX

10、;/轉(zhuǎn)換表節(jié)點(diǎn)數(shù)組char transword;/轉(zhuǎn)換條件int NumTn;/添加的頂點(diǎn)數(shù)*TableQueue; typedef struct transmatrix/狀態(tài)轉(zhuǎn)換矩陣TableQueue TQ;/轉(zhuǎn)換表列組int transnum;/轉(zhuǎn)換表列數(shù)*TranMatrix; int GraphEmpty(Graph g)/圖判空return g-NumVertex=0; int GraphFull(Graph g)/判圖滿return g-NumVertex=g-MaxNumVertex; char GetValue(Graph g,int i)/尋找下標(biāo)為i的頂點(diǎn)return (

11、i0 & iNumVertex? g-NodeTablei.data: ); void Insert_Vertex(Graph g,char vertex)/插入新的頂點(diǎn)g-NodeTableg-NumVertex.data=vertex;g-NodeTableg-NumVertex.adj=NULL;g-NumVertex+; void Insert_Edge(Graph g,int v1,int v2,char weight)/插入邊Edge p;p=(Edge)malloc(sizeof(struct edge);p-cost=weight;p-dest=v2;p-link=g-Node

12、Tablev1.adj;g-NodeTablev1.adj=p; int GetVertexPos(Graph g,char v)/得到頂點(diǎn)在圖中的下標(biāo)int i=0;while(iNumVertex)if(g-NodeTablei.data=v)return i;i+;return INFINIT; void Construct_Graph(Graph g)/創(chuàng)建圖int k,j,i,vexn,edgen;char head,tail,name;char weight;g-NumVertex=0;g-NumEdge=0;g-MaxNumVertex=MAX;g-NodeTable=(Vert

13、ex)malloc(g-MaxNumVertex)*sizeof(struct vertex);printf(輸入NFA狀態(tài)數(shù):);scanf(%d,&vexn);printf(輸入NFA狀態(tài)名稱:n);flushall();/依次獲取狀態(tài)名稱，并將這些頂點(diǎn)插入圖中for(i=0;ivexn;i+) scanf(%c,&name);flushall();Insert_Vertex(g,name); printf(輸入NFA的邊數(shù):); scanf(%d,&edgen); printf(輸入 起始狀態(tài)，接受字符 和 到達(dá)狀態(tài):n); flushall();/依次獲取邊的信息（起始頂點(diǎn)，接受字符，

14、到達(dá)的頂點(diǎn)），并將這些邊插入圖中for(i=0;iedgen;i+) flushall();scanf(%c %c %c,&tail,&weight,&head);k=GetVertexPos(g,tail);j=GetVertexPos(g,head);Insert_Edge(g,k,j,weight); void Destruct_Graph(Graph g)/銷毀圖 int i;Edge p;for(i=0;iNumVertex;i+)p=g-NodeTablei.adj;while(p!=NULL)g-NodeTablei.adj=p-link;p-link=NULL;free (p)

15、;p=g-NodeTablei.adj;g-NumEdge=0;g-NumVertex=0;printf(圖已銷毀n); void Show_Graph(Graph g)/顯示圖 int i; Edge p;for(i=0;iNumVertex;i+)p=g-NodeTablei.adj;while(p!=NULL)printf(%c,%c):%c ,g-NodeTablei.data,g-NodeTablep-dest.data,p-cost);p=p-link;printf(n);void Init_Matrix(TranMatrix TM)int i,j,k;printf(輸入接受字符數(shù)

16、:);scanf(%d,&TM-transnum);TM-TQ=(TableQueue)malloc(TM-transnum+1)*sizeof(struct tablequeue);/初始化轉(zhuǎn)換矩陣的第一列for(j=0;jTQ0.TNj=(TableNode)malloc(sizeof(struct tablenode);TM-TQ0.TNj-newname=0;for(k=0;kTQ0.TNj-chk=0;TM-TQ0.transword=I;TM-TQ0.NumTn=0;/初始化轉(zhuǎn)換矩陣的其它列for(i=1;itransnum;i+)printf(輸入第%d個(gè)轉(zhuǎn)換字符:n,i);fl

17、ushall();scanf(%c,&TM-TQi.transword);for(j=0;jTQi.TNj=(TableNode)malloc(sizeof(struct tablenode);TM-TQi.TNj-newname=0;for(k=0;kTQi.TNj-chk=0;TM-TQi.NumTn=0;void BubbleSort(char a,int len)/冒泡排序int i,j;char temp; for(i=0;ilen;i+)for(j=0;jaj+1)temp=aj+1;aj+1=aj;aj=temp; int CheckChar(char t,char ti)/檢查

18、數(shù)組t中是否有與ti相同的字符/0 有重復(fù)，1 無重復(fù)int i;for(i=0;iNumMaxChar;i+)if(ti=ti) return 0;return 1; int CheckTable(TranMatrix TM,char str)/檢查轉(zhuǎn)換矩陣的第一列中是否有與str相同的字符串/ i 有重復(fù)（并返回重復(fù)的位置），1 無重復(fù)int i;for(i=0;iTQ0.NumTn;i+)if(!strcmp(TM-TQ0.TNi-ch,str)return i;return 1; void Smove(Graph g,char t1,char t2,char transword)/根據(jù)

19、NFA，將t1中的狀態(tài)接受了transword后轉(zhuǎn)為對(duì)應(yīng)的t2中的狀態(tài)int i,j,k=0,check,len;Edge p;while(t2k!=0) k+;for(i=0;iMAX;i+)for(j=0;jNumVertex;j+)if(g-NodeTablej.data=t1i) p=g-NodeTablej.adj;while(p!=NULL)if(p-cost=transword) check=CheckChar(t2,g-NodeTablep-dest.data);if(check=1) t2k=g-NodeTablep-dest.data;k+;p=p-link;elsep=p

20、-link;len=k;BubbleSort(t2,k); void E_Closure(Graph g,char t)/對(duì)進(jìn)行了Smove后的狀態(tài)集合求閉包，并將結(jié)果按升序排列int i=0,j,k=0,check,len;Edge p;/找到字符數(shù)組中的最后一個(gè)字符的位置while(tk!=0) k+;for(i=0;ti!=0;i+) /每個(gè)頂點(diǎn)都要查看一次for(j=0;jNumVertex;j+)/if(g-NodeTablej.data=ti)p=g-NodeTablej.adj;while(p!=NULL)if(p-cost=*)/空輸入 check=CheckChar(t,g-

21、NodeTablep-dest.data);if(check=1)tk=g-NodeTablep-dest.data;k+; p=p-link;len=k;BubbleSort(t,k);/結(jié)果按升序排列 void Show_TranMatrix(TranMatrix TM)int i,j,k;printf(狀態(tài)轉(zhuǎn)換矩陣:n);for(j=0;jtransnum;j+) printf(轉(zhuǎn)換字符:%c ,TM-TQj.transword);printf(n);for(k=0;kMAX;k+) for(j=0;jtransnum;j+) if(TM-TQj.TNk-newname=0) print

22、f(NULL );else printf(%c:,TM-TQj.TNk-newname);for(i=0;TM-TQj.TNk-chi!=0;i+) printf(%c,TM-TQj.TNk-chi);if(TM-TQj.TNk-ch0=0) printf(NULL);printf( );printf(n); void NFA_to_DFA(Graph g,TranMatrix TM)int j=0,i,check;char temp2=0,0;TM-TQ0.TN0-ch0=g-NodeTable0.data;for(i=1;itransnum;i+)E_Closure(g,TM-TQ0.TN0-ch);printf(輸入新狀態(tài)名:);flushall();scanf(%c,&TM-TQ0.TN0-newname);TM-TQ0.NumTn+;while(jTQ0.NumTn)for(i=1;itransnum;i+)Smove(g,TM-TQ0.TNj-ch,TM-TQi.TNj-ch,TM-TQi.transword);E_Closure(g,TM-TQi.TNj-ch);if (TM-TQi.TNj-ch0!=0)/如果為空則可忽略，不記入結(jié)果狀態(tài)check=CheckTable(TM,TM-TQi.TNj-ch);if(check=1) printf(輸入新狀態(tài)名:)