編譯原理課程設(shè)計--nfa轉(zhuǎn)化為dfa的轉(zhuǎn)換算法及實現(xiàn)

1、<p>　　編譯原理課程實踐報告</p><p>　　設(shè)計名稱： NFA轉(zhuǎn)化為DFA的轉(zhuǎn)換算法及實現(xiàn) </p><p>　　二級學(xué)院： 數(shù)學(xué)與計算機科學(xué)學(xué)院 </p><p>　　專 業(yè)： 計算機科學(xué)與技術(shù) </p><p>　　班 級： 計科本091班

2、 </p><p>　　姓 名： 林玉蘭 </p><p>　　學(xué) 號： 0904402102 </p><p>　　指導(dǎo)老師： 梁德塞 </p><p>　　日

3、期： 2012年6月 </p><p><b>　　摘要</b></p><p>　　確定有限自動機確定的含義是在某種狀態(tài)，面臨一個特定的符號只有一個轉(zhuǎn)換，進入唯一的一個狀態(tài)。不確定的有限自動機則相反，在某種狀態(tài)下，面臨一個特定的符號是存在不止一個轉(zhuǎn)換，即是可以允許進入一個狀態(tài)集合。</p><p>　　

4、在非確定的有限自動機NFA中,由于某些狀態(tài)的轉(zhuǎn)移需從若干個可能的后續(xù)狀態(tài)中進行選擇，故一個NFA對符號串的識別就必然是一個試探的過程。這種不確定性給識別過程帶來的反復(fù)，無疑會影響到FA的工作效率。而DFA則是確定的,將NFA轉(zhuǎn)化為DFA將大大提高工作效率,因此將NFA轉(zhuǎn)化為DFA是有其一定必要的。</p><p>　　對于任意的一個不確定有限自動機（NFA）都會存在一個等價的確定的有限自動機（DFA），即L(N)

5、=L(M)。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價的簡化的DFA，通過具體實例，結(jié)合圖形，詳細說明轉(zhuǎn)換的算法原理。</p><p>　　關(guān)鍵詞：有限自動機；確定有限自動機（DFA），不確定有限自動機（NFA）</p><p><b>　　Abstract</b></p><p>　　Finite automata is determinate

6、 and indeterminate two class. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces

7、 a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.</p><p>　　Non deterministic finite state automata NFA, because of some state are transferred from

8、a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency o

9、f the FA. While the DFA is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.</p><p>　　For any a nondeterministic finite automaton ( N

10、FA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detai

11、led description of the algorithm principle of conversion.</p><p>　　Keywords:：finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA </p><p><b>　　目

12、錄</b></p><p><b>　　1.前言：1</b></p><p><b>　　1.1背景1</b></p><p><b>　　1.2實踐目的1</b></p><p>　　1.2課程實踐的意義1</p><p>　　2.

13、NFA和DFA的概念2</p><p>　　2.1 不確定有限自動機NFA2</p><p>　　2.2確定有限自動機DFA3</p><p>　　3．從NDF到DFA的等價變化步驟5</p><p><b>　　3.1轉(zhuǎn)換思路5</b></p><p>　　3.2.消除空轉(zhuǎn)移5<

14、;/p><p>　　3.3子集構(gòu)造法7</p><p><b>　　4程序?qū)崿F(xiàn)9</b></p><p>　　4.1程序框架圖9</p><p>　　4.2 數(shù)據(jù)流程圖9</p><p>　　4.3實現(xiàn)代碼10</p><p>　　4.4運行環(huán)境10</p&g

15、t;<p>　　4.5程序?qū)崿F(xiàn)結(jié)果10</p><p><b>　　5.用戶手冊12</b></p><p>　　6.課程總結(jié)：12</p><p>　　7.參 考 文 獻12</p><p><b>　　8. 附錄13</b></p><p><

16、;b>　　1.前言：</b></p><p><b>　　1.1背景</b></p><p>　　有限自動機作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合，引入有窮自動機這個理論，正是為詞法分析程序的自動構(gòu)造尋找特殊的方法和工具。 有限自動機（Finite Automate）是用來模擬實物系統(tǒng)的數(shù)學(xué)模型

17、，它包括如下五個部分：</p><p>　　有窮狀態(tài)集States </p><p>　　輸入字符集Input symbols </p><p>　　轉(zhuǎn)移函數(shù)Transitions </p><p>　　起始狀態(tài)Start state </p><p>　　接受狀態(tài)Accepting state(s) </p&g

18、t;<p><b>　　1.2實踐目的</b></p><p>　?。?）設(shè)計、編制、調(diào)式一個有窮自動機程序，加深對NFA轉(zhuǎn)換為DFA的原理的理解。</p><p>　?。?）掌握NFA確定化的過程。</p><p>　　1.2課程實踐的意義</p><p>　　通過本課程設(shè)計教學(xué)所可以使我們充分理解和掌握

19、NFA，DFA以及NFA確定化過程的相關(guān)概念和知識，理解和掌握子集法的相關(guān)知識和應(yīng)用，編程實現(xiàn)對輸入NFA轉(zhuǎn)換成DFA輸出的功能。</p><p>　　2.NFA和DFA的概念</p><p>　　2.1 不確定有限自動機NFA</p><p>　　NFA(nondeterministic finite-state automata)即非確定有限自動機, 一個非確定

20、的有限自動機NFA M’是一個五元式:</p><p>　　NFA M’=(S, Σ∪{ε}, δ, S0, F)</p><p>　　其中 S—有限狀態(tài)集，Σ∪{ε}—輸入符號加上ε,即自動機的每個結(jié)點所射出的弧可以是Σ中一個字符或是ε.</p><p>　　S0—初態(tài)集 F—終態(tài)集 </p><p&

21、gt;　　δ—轉(zhuǎn)換函數(shù) S×Σ ∪{ε} →2S </p><p>　　(2S --S的冪集—S的子集構(gòu)成的集合）</p><p>　　例1： NFA M=({S,P,Z},{0,1},f,{s,p},{z})</p><p><b>　　其中</b></p><p>　　f(s,0)={p}

22、 f(z,0)={p} f(p,1)={z}</p><p>　　f(z,1)={p} f(s,1)={s,z}</p><p>　?、貼FA的狀態(tài)圖表示如下：</p><p><b>　　②NFA矩陣表示：</b></p><p>　　2.2確定有限自動機DFA</p>

23、<p>　　DFA(deterministic finite-state automata)即確定有限自動機，一個確定的有限自動機DFA M是一個五元式:</p><p>　　M=(S, Σ，δ, S0, Z) </p><p><b>　　其中:</b></p><p><b>　　S —有限狀態(tài)集</b>

24、;</p><p><b>　　Σ —輸入字母表</b></p><p>　　δ —映射函數(shù)(也稱狀態(tài)轉(zhuǎn)換函數(shù))</p><p><b>　　S×Σ→S</b></p><p>　　δ(s,a)=S’ , S, S’ ∈S, a∈Σ</p><p>　　S0 —初

25、始狀態(tài) S0 ∈S</p><p>　　Z—終止?fàn)顟B(tài)集 ZS</p><p>　　例2：DFA M=({S,U,V,Q},{a,b},f,s,{Q}) 其中f的定義為：</p><p>　　f(S,a)=U f(S,b)=V f(U,a)=Q f(U,b)=V</p>&l

26、t;p>　　f(V,a)=U f(V,b)=Q f(Q,a)=Q f(Q,b)=Q</p><p>　　DFA的狀態(tài)圖表示：</p><p>　　假如DFA M含有m個狀態(tài)，n個輸入符，那么這個狀態(tài)含有m個節(jié)點，每個節(jié)點最多有n個弧射出，整個圖整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點用雙圈表

27、示或標(biāo)以“+”，若 f(ki ,a)=kj，則從狀態(tài)結(jié)點ki到狀結(jié)點kj畫標(biāo)記為a的?。?lt;/p><p><b>　　DFA矩陣表示：</b></p><p>　　一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭=>標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在

28、表的右端標(biāo)以1，非終態(tài)標(biāo)以0.</p><p>　　3．從NDF到DFA的等價變化步驟</p><p>　　事實已經(jīng)證明了不管是非確定的有限自動機M還是具有ε-轉(zhuǎn)移的非確定的有限自動機，都可以找到一個與之等價的確定有限自動機，使得L（M）=L（M’）。</p><p><b>　　3.1轉(zhuǎn)換思路</b></p><p>

29、　　由非確定的有限自動機出發(fā)構(gòu)造與之等價的確定的有限自動機的辦法是確定的有限自動機的狀態(tài)對應(yīng)于非確定的有限自動機的狀態(tài)集合，即要使轉(zhuǎn)換后的DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài)。該DFA使用它的狀態(tài)去記錄在NFA讀入一個輸入符號后可能到達的所有狀態(tài)，也就是說，在讀入符號串a(chǎn)1a2a3…an之后，該DFA處在這樣一個狀態(tài)，該狀態(tài)表示這個NFA的狀態(tài)的一個子集T，而T是從NFA的開始狀態(tài)沿著某個標(biāo)記為a1a2a3…an的路徑可以到達的那些狀

30、態(tài)。</p><p><b>　　3.2.消除空轉(zhuǎn)移</b></p><p>　　.消除N形式的產(chǎn)生式，即消除空轉(zhuǎn)移。狀態(tài)集合I的a弧轉(zhuǎn)換Ia:定義為一狀態(tài)集，是指從狀態(tài)集I出發(fā)先經(jīng)過a弧后再經(jīng)過若干條ε弧而能到達的狀態(tài)的集合?？梢詫懽鳎?Ia= ε-closure(J)，J=move(I,a),其中，J是從I中任一狀態(tài)出發(fā)經(jīng)過一條a弧到達的狀態(tài)集合，記為move(I

31、,a)。</p><p>　　s 表示NFA的狀態(tài)，T 表示NFA的狀態(tài)集合，a表示一個input symbol</p><p>　　ε-transition(ε轉(zhuǎn)換)就是說input symbol為ε時的transition(轉(zhuǎn)換) </p><p><b>　　例如：</b></p><p>　　對于以下狀態(tài)圖中：

32、ε-closure({0})={0,1,2,4,7}</p><p>　　在這里設(shè)I={0,1,2,4,7}，則因為有move(I,a)={3,8}=J,所以</p><p>　　Ia= ε-closure(J)= ε-closure({3,8})={1,2,3,4,6,7,8}</p><p><b>　　3.3子集構(gòu)造法</b></p

33、><p>　　確定化每個多重轉(zhuǎn)移，即拆分多值函數(shù)為單位函數(shù),具體轉(zhuǎn)換，采用子集構(gòu)造法。</p><p>　　以下面的基于字母表Σ={a,b}上的具有ε-轉(zhuǎn)移的非確定有限自動機M為例。</p><p>　　步驟1：以I，Ia、Ib等為列做表，其中I列第一行的內(nèi)容是初態(tài)的ε- 閉包所得到的狀態(tài)集合。并以此為I計算Ia、Ib等，而 且在所計算出的Ia、Ib等中若有新的狀態(tài)集產(chǎn)

34、生，就重復(fù)以此新的集合為I再此計算Ia、Ib等，直到在所得的Ia、Ib等中不再產(chǎn)生新的狀態(tài)集為止。</p><p>　　步驟2：在上表中將原NFA初態(tài)的ε-閉包作為轉(zhuǎn)換后的DFA的初態(tài)，包含原NFA終態(tài)的狀態(tài)作為轉(zhuǎn)換后的DFA的終態(tài)，并進行重新編號得到轉(zhuǎn)換后的DFA的狀態(tài)轉(zhuǎn)移矩陣如下：</p><p>　　步驟3：畫出轉(zhuǎn)換后的DFA的狀態(tài)圖：</p><p><

35、;b>　　4程序?qū)崿F(xiàn)</b></p><p><b>　　4.1程序框架圖</b></p><p><b>　　4.2 數(shù)據(jù)流程圖</b></p><p><b>　　4.3實現(xiàn)代碼</b></p><p><b>　　（見附錄）</b>

36、</p><p><b>　　4.4運行環(huán)境</b></p><p>　　（1）開發(fā)平臺：Microsoft visual C++6.0 </p><p>　?。?）運行平臺：Windows xp/Windows 2000</p><p><b>　　4.5程序?qū)崿F(xiàn)結(jié)果</b></p>

37、<p><b>　　實現(xiàn)NFA例題為：</b></p><p>　　NFA M=({S,P,Z},{0,1},f,{s,p},{z})</p><p><b>　　其中</b></p><p>　　f(s,0)={p} f(z,0)={p} f(p,1)={z}</p>

38、;<p>　　f(z,1)={p} f(s,1)={s,z}</p><p>　　根據(jù)例題輸入NFA各邊的信息得出結(jié)果如下圖：</p><p><b>　　5.用戶手冊</b></p><p>　　本程序應(yīng)在Microsoft Visual C++ 6.0下運行。NFA的確定化是編譯過程中一個重要的部分，由于本程序的

39、輸入很多，而且有多種格式的輸入，所以輸入時必須非常小心細致。對于狀態(tài)轉(zhuǎn)換矩陣的表示，冒號前的是新狀態(tài)名，冒號后的是舊狀態(tài)名。對于轉(zhuǎn)化后的DFA表示，3個數(shù)據(jù)分別表示為起始狀態(tài)、接受字符和到達狀態(tài)，例如（0,1,1）表示為新狀態(tài)0接受字符1到達新字符狀態(tài)1。運行結(jié)果因為轉(zhuǎn)換字符輸入順序的不同，得出的結(jié)果有可能與筆算得出的順序有所不同，但是結(jié)果依然是正確。</p><p><b>　　6.課程總結(jié)：<

40、/b></p><p>　　通過這次課程實踐設(shè)計，讓我對課堂上老師所講到的不確定和確定有限自動機有了更深的理解，理解了它們的構(gòu)造和怎樣相互轉(zhuǎn)化。很好的理解了子集法的演算過程。經(jīng)過多次試驗，在正確輸入相關(guān)數(shù)據(jù)的情況下，程序能正常運行，當(dāng)錯誤操作或輸入錯誤數(shù)據(jù)時，程序?qū)?yīng)錯誤自動關(guān)閉。經(jīng)過這次課程設(shè)計,也讓我深刻的認(rèn)識到實踐才是最重要的。書本只能教給我們基礎(chǔ)知識,要怎樣運用,將那些知識真正吸收,轉(zhuǎn)化為自己的智慧

41、,只有通過實踐才能達到。編譯原理是一門實用性很強，對我們的專業(yè)很有幫助的科目,我將會繼續(xù)努力,不斷增加自己的知識面,把編譯原理學(xué)習(xí)的更好。</p><p>　　同時我也發(fā)現(xiàn)自己對于有限自動機的知識掌握得還不是很多，在這次課程實踐中，我懂得了怎樣去和別人交流，更好地掌握和熟練了所學(xué)的知識。</p><p><b>　　7.參 考 文 獻</b></p>&

42、lt;p>　?。?）楊路明、郭浩志.C語言程序設(shè)計教程.2003年12月第1版. 北京:北京郵電大學(xué)出版社.2005</p><p>　?。?）陳火旺.程序設(shè)計語言編譯原理.2000年1月第3版. 北京:國防工業(yè)出版社.2006.46-51</p><p>　　（3）嚴(yán)蔚敏、吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.1997年4月第1版.北京:清華大學(xué)出版社.2005</p>&l

43、t;p>　?。?）王曉東編著.計算機算法設(shè)計與分析.電子工業(yè)出版社.2004</p><p><b>　　8. 附錄</b></p><p>　　NFA轉(zhuǎn)換為DFA采用C++編程實現(xiàn)代碼如下</p><p>　　#include<iostream></p><p>　　#include<strin

44、g></p><p>　　#define MAXS 100</p><p>　　using namespace std;</p><p>　　string NODE; //結(jié)點集合</p><p>　　string CHANGE; //終結(jié)符集合</p><p>　　int N; //NFA邊數(shù)</p

45、><p>　　struct edge{</p><p>　　string first;</p><p>　　string change;</p><p>　　string last;</p><p><b>　　};</b></p><p>　　struct chan{<

46、/p><p>　　string ltab;</p><p>　　string jihe[MAXS];</p><p><b>　　};</b></p><p>　　void kong(int a)</p><p><b>　　{</b></p><p>&

47、lt;b>　　int i;</b></p><p>　　for(i=0;i<a;i++)</p><p>　　cout<<' ';</p><p><b>　　}</b></p><p><b>　　//排序</b></p><

48、p>　　void paixu(string &a)</p><p><b>　　{</b></p><p><b>　　int i,j;</b></p><p><b>　　char b;</b></p><p>　　for(j=0;j<a.length()

49、;j++)</p><p>　　for(i=0;i<a.length();i++)</p><p>　　if(NODE.find(a[i])>NODE.find(a[i+1]))</p><p><b>　　{</b></p><p><b>　　b=a[i];</b></p>

50、;<p>　　a[i]=a[i+1];</p><p><b>　　a[i+1]=b;</b></p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　void eclouse(char c,string &h

51、e,edge b[])</p><p><b>　　{</b></p><p><b>　　int k;</b></p><p>　　for(k=0;k<N;k++)</p><p><b>　　{</b></p><p>　　if(c==b[k]

52、.first[0])</p><p>　　if(b[k].change=="*")</p><p><b>　　{</b></p><p>　　if(he.find(b[k].last)>he.length())</p><p>　　he+=b[k].last;</p><p

53、>　　eclouse(b[k].last[0],he,b);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void move(chan &he,int m,edge b

54、[])</p><p><b>　　{</b></p><p>　　int i,j,k,l;</p><p>　　k=he.ltab.length();</p><p>　　l=he.jihe[m].length();</p><p>　　for(i=0;i<k;i++)</p>

55、<p>　　for(j=0;j<N;j++)</p><p>　　if((CHANGE[m]==b[j].change[0])&&(he.ltab[i]==b[j].first[0]))</p><p>　　if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())</p><p&

56、gt;　　he.jihe[m]+=b[j].last[0]; </p><p>　　for(i=0;i<l;i++)</p><p>　　for(j=0;j<N;j++)</p><p>　　if((CHANGE[m]==b[j].change[0])&&(he.jihe[m][i]==b[j].first[0]))</p>

57、<p>　　if(he.jihe[m].find(b[j].last[0])>he.jihe[m].length())</p><p>　　he.jihe[m]+=b[j].last[0];</p><p><b>　　}</b></p><p><b>　　//輸出</b></p><

58、;p>　　void outputfa(int len,int h,chan *t)</p><p><b>　　{</b></p><p>　　int i,j,m;</p><p>　　cout<<" I ";</p><p>　　for(i=0;i<len;i++

59、)</p><p>　　cout<<'I'<<CHANGE[i]<<" ";</p><p>　　cout<<endl<<"-------------------------"<<endl;</p><p>　　for(i=0;i

60、<h;i++)</p><p><b>　　{</b></p><p>　　cout<<' '<<t[i].ltab;</p><p>　　m=t[i].ltab.length();</p><p>　　for(j=0;j<len;j++)</p><

61、;p><b>　　{</b></p><p>　　kong(8-m);</p><p>　　m=t[i].jihe[j].length();</p><p>　　cout<<t[i].jihe[j];</p><p><b>　　}</b></p><p>

62、　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　edge *b=new edg

63、e[MAXS];</p><p>　　int i,j,k,m,n,h,x,y,len;</p><p>　　bool flag;</p><p>　　string jh[MAXS],endnode,ednode,sta;</p><p>　　cout<<"請輸入NFA各邊信息,分別為 ：起點 條件[空為*] 終點，最后

64、以#結(jié)束："<<endl;</p><p>　　for(i=0;i<MAXS;i++)</p><p><b>　　{</b></p><p>　　cin>>b[i].first;</p><p>　　if(b[i].first=="#") break;<

65、/p><p>　　cin>>b[i].change>>b[i].last;</p><p><b>　　}</b></p><p><b>　　N=i;</b></p><p>　　/*for(j=0;j<N;j++)</p><p>　　cout&

66、lt;<b[j].first<<b[j].change<<b[j].last<<endl;*/</p><p>　　for(i=0;i<N;i++)</p><p><b>　　{</b></p><p>　　if(NODE.find(b[i].first)>NODE.length())&l

67、t;/p><p>　　NODE+=b[i].first;</p><p>　　if(NODE.find(b[i].last)>NODE.length())</p><p>　　NODE+=b[i].last;</p><p>　　if((CHANGE.find(b[i].change)>CHANGE.length())&&am

68、p;(b[i].change!="*"))</p><p>　　CHANGE+=b[i].change;</p><p><b>　　}</b></p><p>　　len=CHANGE.length();</p><p>　　cout<<"結(jié)點中屬于終態(tài)的是："<

69、;<endl;</p><p>　　cin>>endnode;</p><p>　　for(i=0;i<endnode.length();i++)</p><p>　　if(NODE.find(endnode[i])>NODE.length())</p><p><b>　　{</b><

70、;/p><p>　　cout<<"所輸終態(tài)不在集合中，錯誤！"<<endl;</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　//cout<<"endnode="&

71、lt;<endnode<<endl;</p><p>　　chan *t=new chan[MAXS]; </p><p>　　t[0].ltab=b[0].first;</p><p><b>　　h=1;</b></p><p>　　eclouse(b[0].first[0],t[0].ltab,b

72、); //求e-clouse</p><p>　　//cout<<t[0].ltab<<endl;</p><p>　　for(i=0;i<h;i++)</p><p><b>　　{ </b></p><p>　　for(j=0;j<t[i].ltab.length();

73、j++)</p><p>　　for(m=0;m<len;m++)</p><p>　　eclouse(t[i].ltab[j],t[i].jihe[m],b); //求e-clouse</p><p>　　for(k=0;k<len;k++)</p><p><b>　　{</b></p>

74、<p>　　//cout<<t[i].jihe[k]<<"->";</p><p>　　move(t[i],k,b); //求move(I,a)</p><p>　　//cout<<t[i].jihe[k]<<endl;</p><p>　　for(j=0;j&l

75、t;t[i].jihe[k].length();j++)</p><p>　　eclouse(t[i].jihe[k][j],t[i].jihe[k],b); //求e-clouse</p><p><b>　　}</b></p><p>　　for(j=0;j<len;j++)</p><p><b>

76、　　{</b></p><p>　　paixu(t[i].jihe[j]); //對集合排序以便比較</p><p>　　for(k=0;k<h;k++)</p><p><b>　　{</b></p><p>　　flag=operator==(t[k].ltab,t[i].jihe[j]);&l

77、t;/p><p><b>　　if(flag)</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　if(!flag&&t[i].jihe[j].length())</p><p&

78、gt;　　t[h++].ltab=t[i].jihe[j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　cout<<endl<<"狀態(tài)轉(zhuǎn)換矩陣如下："<<endl;</p><p>　　

79、outputfa(len,h,t); //輸出狀態(tài)轉(zhuǎn)換矩陣</p><p><b>　　//狀態(tài)重新命名</b></p><p>　　string *d=new string[h];</p><p>　　NODE.erase();</p><p>　　cout<<endl<<"重命名

80、："<<endl;</p><p>　　for(i=0;i<h;i++) </p><p><b>　　{</b></p><p>　　sta=t[i].ltab;</p><p>　　t[i].ltab.erase(); </p><p>　　t[i].ltab=

81、'A'+i;</p><p>　　NODE+=t[i].ltab;</p><p>　　cout<<'{'<<sta<<"}="<<t[i].ltab<<endl;</p><p>　　for(j=0;j<endnode.length();j++)&

82、lt;/p><p>　　if(sta.find(endnode[j])<sta.length())</p><p>　　d[1]=ednode+=t[i].ltab;</p><p>　　for(k=0;k<h;k++)</p><p>　　for(m=0;m<len;m++)</p><p>　　if(

83、sta==t[k].jihe[m])</p><p>　　t[k].jihe[m]=t[i].ltab;</p><p><b>　　}</b></p><p>　　for(i=0;i<NODE.length();i++)</p><p>　　if(ednode.find(NODE[i])>ednode.le

84、ngth())</p><p>　　d[0]+=NODE[i];</p><p>　　endnode=ednode;</p><p>　　cout<<endl<<"DFA如下："<<endl;</p><p>　　outputfa(len,h,t); //輸出DFA</p&g

85、t;<p>　　cout<<"其中終態(tài)為："<<endnode<<endl;</p><p><b>　　//DFA最小化</b></p><p><b>　　m=2;</b></p><p>　　sta.erase();</p><

86、p><b>　　flag=0; </b></p><p>　　for(i=0;i<m;i++)</p><p><b>　　{</b></p><p>　　//cout<<"d["<<i<<"]="<<d[i]<<

87、;endl;</p><p>　　for(k=0;k<len;k++)</p><p><b>　　{</b></p><p>　　//cout<<"I"<<CHANGE[k]<<endl;</p><p><b>　　y=m;</b>&

88、lt;/p><p>　　for(j=0;j<d[i].length();j++)</p><p><b>　　{</b></p><p>　　for(n=0;n<y;n++)</p><p><b>　　{</b></p><p>　　if(d[n].find(t[N

89、ODE.find(d[i][j])].jihe[k])<d[n].length()||t[NODE.find(d[i][j])].jihe[k].length()==0)</p><p><b>　　{</b></p><p>　　if(t[NODE.find(d[i][j])].jihe[k].length()==0) </p><p>

90、;<b>　　x=m;</b></p><p><b>　　else </b></p><p><b>　　x=n;</b></p><p>　　if(!sta.length()) </p><p><b>　　{</b></p><p

91、>　　sta+=x+48;</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　if(sta[0]!=x+48)</p><p><b>　　{</b></p><p>　　d[m]+=d[i]

92、[j];</p><p><b>　　flag=1;</b></p><p>　　d[i].erase(j,1);</p><p>　　//cout<<d[i]<<endl;</p><p><b>　　j--;</b></p><p><b&g

93、t;　　}</b></p><p>　　break; //跳出n</p><p><b>　　}</b></p><p><b>　　}//n</b></p><p><b>　　}//j</b></p><p><b>　　if(

94、flag)</b></p><p><b>　　{</b></p><p><b>　　m++;</b></p><p><b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　/

95、/cout<<"sta="<<sta<<endl;</p><p>　　sta.erase();</p><p><b>　　}//k</b></p><p><b>　　}//i</b></p><p>　　cout<<endl&

96、lt;<"集合劃分：";</p><p>　　for(i=0;i<m;i++)</p><p>　　cout<<"{"<<d[i]<<"} ";</p><p>　　cout<<endl;</p><p><b>

97、　　//狀態(tài)重新命名</b></p><p>　　chan *md=new chan[m]; </p><p>　　NODE.erase();</p><p>　　cout<<endl<<"重命名："<<endl;</p><p>　　for(i=0;i<m;i++)

98、 </p><p><b>　　{</b></p><p>　　md[i].ltab='A'+i; </p><p>　　NODE+=md[i].ltab;</p><p>　　cout<<"{"<<d[i]<<"}="<&

99、lt;md[i].ltab<<endl;</p><p><b>　　}</b></p><p>　　for(i=0;i<m;i++)</p><p>　　for(k=0;k<len;k++)</p><p>　　for(j=0;j<h;j++)</p><p>&l

100、t;b>　　{</b></p><p>　　if(d[i][0]==t[j].ltab[0])</p><p><b>　　{</b></p><p>　　for(n=0;n<m;n++)</p><p><b>　　{</b></p><p>　　i

101、f(!t[j].jihe[k].length())</p><p><b>　　break;</b></p><p><b>　　else</b></p><p>　　if(d[n].find(t[j].jihe[k])<d[n].length())</p><p><b>　　{&

102、lt;/b></p><p>　　md[i].jihe[k]=md[n].ltab;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>

103、;　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　ednode.erase();</p><p>　　for(i=0;i<m;i++)</p><p>　　for(j=0;j<

104、;endnode.length();j++)</p><p>　　if(d[i].find(endnode[j])<d[i].length()&&ednode.find(md[i].ltab))</p><p>　　ednode+=md[i].ltab;</p><p>　　endnode=ednode;</p><p>

105、;　　cout<<endl<<"最小化DFA如下："<<endl;</p><p>　　outputfa(len,m,md); </p><p>　　cout<<"其中終態(tài)為："<<endnode<<endl;</p><p><b>　　}&l