不確定有窮自動機的確定化

1、編譯原理實驗報告不確定有限狀態(tài)自動機的確定化實驗名稱 2011/5/23實驗時間 計算機科學(xué)與技術(shù)專業(yè)院系 08計算機一班班級 E學(xué)號 王全鴻姓名 1. 試驗?zāi)康妮斎耄?非確定有限（窮）狀態(tài)自動機。輸出： 確定化的有限（窮）狀態(tài)自動機2. 實驗原理一個確定的有限自動機（DFA）M可以定義為一個五元組，M（K，F(xiàn)，S，Z），其中：（1） K是一個有窮非空集，集合中的每個元素稱為一個狀態(tài)；（2） 是一個有窮字母表，中的每個元素稱為一個輸入符號；（3） F是一個從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，是一個終態(tài)集。由定義可見，確定有限自動機只有惟一的一個初態(tài)，但可以有多個終態(tài)，每個狀態(tài)對字母表中的任一輸入符號，最多只有一個后繼狀態(tài)。 對于DFA M，若存在一條從某個初態(tài)結(jié)點到某一個終態(tài)結(jié)點的通路，則稱這條通路上的所有弧的標(biāo)記符連接形成的字符串可為DFA M所接受。若M的初態(tài)結(jié)點同時又是終態(tài)結(jié)點，則稱可為M所接受（或識別），DFA M所能接受的全部字符串（字）組成的集合記作L（M）。一個不確定有限自動機（NFA）M可以定義為一個五元組，M（K，F(xiàn)，S，Z），其中：（1） k是一個有窮非空集，集合中的每個元素稱為一個狀態(tài)；（2） 是一個有窮字母表，中的每個元素稱為

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

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

5、自動機，通常都是確定有限自動機DFA，因此這就需要將不確定有限自動機轉(zhuǎn)換成等價的確定有限自動機，這個過程稱為不確定有限自動機的確定化，即NFA確定化為DFA。下面介紹一種NFA的確定化算法，這種算法稱為子集法：（1） 若NFA的全部初態(tài)為S1，S2，Sn，則令DFA的初態(tài)為：SS1，S2，Sn，其中方括號用來表示若干個狀態(tài)構(gòu)成的某一狀態(tài)。（2） 設(shè)DFA的狀態(tài)集K中有一狀態(tài)為Si，Si+1，Sj，若對某符號a，在NFA中有F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 則令F（ Si，Si+1，Sj ，a）= Si，Si+1，Sk 為DFA的一個轉(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)。對于上述NFA確定化算法子集法，還可以采用另一種操作性更強的描述方式，下面我們給出其詳細描述。首先給出兩個相關(guān)定義。 假設(shè)I是NFA M狀態(tài)集K的一個子集（即IK），則定義-closure（I）為：（1） 若QI，則Q-closure（I）；（2） 若QI，則從Q出發(fā)經(jīng)過任意條弧而能到達的任何狀態(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弧而到達的狀態(tài)集。NFA確定化的實質(zhì)是以原有狀態(tài)集上的子集作為DFA上的一個狀態(tài)，將原狀態(tài)間的轉(zhuǎn)換為該子集間的轉(zhuǎn)換，從而把不確定有限自動機確定化。經(jīng)過確定化后，狀態(tài)數(shù)可能增加，而且可能出現(xiàn)一些等價狀態(tài)，這時就需要簡化。3. 實驗內(nèi)容 實現(xiàn)計算閉包closure（I）的算法； 實現(xiàn)轉(zhuǎn)換函數(shù)move（q，a）的算法； 輸出界面如下：NFA的 圖形形式DFA的圖形形式4. 實驗心得本次實驗對我來說是非常困難的，因為我以往的編程經(jīng)驗匱乏，

8、故滿腔墨水無從傾灑。所以，本次的實驗代碼是我從網(wǎng)上下載得來的。雖然代碼不是我所寫，但我可以保證的是程序?qū)嵗俏覄?chuàng)建并自己手動輸入的，對于程序的設(shè)計原理和運行過程我還是相當(dāng)熟練的。針對于這種情況，我已決定以后加強鍛煉，逐步提升自己的編程能力，不僅要做到能讀得懂，也要能寫得出。但此非一朝一夕，希望老師能夠理解。5.實驗代碼#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/頂點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é)點char newname;/新命名char chMAX;/頂點集合*TableNode; typedef struct tablequeue/轉(zhuǎn)換表列TableNode TNMAX

10、;/轉(zhuǎn)換表節(jié)點數(shù)組char transword;/轉(zhuǎn)換條件int NumTn;/添加的頂點數(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的頂點return (

11、i0 & iNumVertex? g-NodeTablei.data: ); void Insert_Vertex(Graph g,char vertex)/插入新的頂點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)/得到頂點在圖中的下標(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)名稱，并將這些頂點插入圖中for(i=0;ivexn;i+) scanf(%c,&name);flushall();Insert_Vertex(g,name); printf(輸入NFA的邊數(shù):); scanf(%d,&edgen); printf(輸入 起始狀態(tài)，接受字符 和 到達狀態(tài):n); flushall();/依次獲取邊的信息（起始頂點，接受字符，

14、到達的頂點），并將這些邊插入圖中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個轉(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)為對應(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)/對進行了Smove后的狀態(tài)集合求閉包，并將結(jié)果按升序排列int i=0,j,k=0,check,len;Edge p;/找到字符數(shù)組中的最后一個字符的位置while(tk!=0) k+;for(i=0;ti!=0;i+) /每個頂點都要查看一次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)名:)