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

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

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

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

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

5、=L(M)。本文主要是介紹如何將NFA轉(zhuǎn)換為與之等價(jià)的簡(jiǎn)化的DFA，通過具體實(shí)例，結(jié)合圖形，詳細(xì)說明轉(zhuǎn)換的算法原理。</p><p>　　關(guān)鍵詞：有限自動(dòng)機(jī)；確定有限自動(dòng)機(jī)（DFA），不確定有限自動(dòng)機(jī)（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實(shí)踐目的1</b></p><p>　　1.2課程實(shí)踐的意義1</p><p>　　2.

13、NFA和DFA的概念2</p><p>　　2.1 不確定有限自動(dòng)機(jī)NFA2</p><p>　　2.2確定有限自動(dòng)機(jī)DFA3</p><p>　　3．從NDF到DFA的等價(jià)變化步驟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實(shí)現(xiàn)代碼10</p><p>　　4.4運(yùn)行環(huán)境10</p&g

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

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

17、，它包括如下五個(gè)部分：</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實(shí)踐目的</b></p><p>　?。?）設(shè)計(jì)、編制、調(diào)式一個(gè)有窮自動(dòng)機(jī)程序，加深對(duì)NFA轉(zhuǎn)換為DFA的原理的理解。</p><p>　?。?）掌握NFA確定化的過程。</p><p>　　1.2課程實(shí)踐的意義</p><p>　　通過本課程設(shè)計(jì)教學(xué)所可以使我們充分理解和掌握

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

20、的有限自動(dòng)機(jī)NFA M’是一個(gè)五元式:</p><p>　　NFA M’=(S, Σ∪{ε}, δ, S0, F)</p><p>　　其中 S—有限狀態(tài)集，Σ∪{ε}—輸入符號(hào)加上ε,即自動(dòng)機(jī)的每個(gè)結(jié)點(diǎn)所射出的弧可以是Σ中一個(gè)字符或是ε.</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>　?、贜FA矩陣表示：</b></p><p>　　2.2確定有限自動(dòng)機(jī)DFA</p>

23、<p>　　DFA(deterministic finite-state automata)即確定有限自動(dòng)機(jī)，一個(gè)確定的有限自動(dòng)機(jī)DFA M是一個(gè)五元式:</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個(gè)狀態(tài)，n個(gè)輸入符，那么這個(gè)狀態(tài)含有m個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多有n個(gè)弧射出，整個(gè)圖整個(gè)圖含有唯一一個(gè)初態(tài)結(jié)點(diǎn)和若干個(gè)終態(tài)結(jié)點(diǎn)，初態(tài)結(jié)點(diǎn)冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點(diǎn)用雙圈表

27、示或標(biāo)以“+”，若 f(ki ,a)=kj，則從狀態(tài)結(jié)點(diǎn)ki到狀結(jié)點(diǎn)kj畫標(biāo)記為a的?。?lt;/p><p><b>　　DFA矩陣表示：</b></p><p>　　一個(gè)DFA還可以用一個(gè)矩陣表示，該矩陣的行表示狀態(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的等價(jià)變化步驟</p><p>　　事實(shí)已經(jīng)證明了不管是非確定的有限自動(dòng)機(jī)M還是具有ε-轉(zhuǎn)移的非確定的有限自動(dòng)機(jī)，都可以找到一個(gè)與之等價(jià)的確定有限自動(dòng)機(jī)，使得L（M）=L（M’）。</p><p><b>　　3.1轉(zhuǎn)換思路</b></p><p>

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

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)過若干條ε弧而能到達(dá)的狀態(tài)的集合?？梢詫懽鳎?Ia= ε-closure(J)，J=move(I,a),其中，J是從I中任一狀態(tài)出發(fā)經(jīng)過一條a弧到達(dá)的狀態(tài)集合，記為move(I

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

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

34、生，就重復(fù)以此新的集合為I再此計(jì)算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)，并進(jìn)行重新編號(hào)得到轉(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實(shí)現(xiàn)代碼</b></p><p><b>　?。ㄒ姼戒洠?lt;/b>

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

37、<p><b>　　實(shí)現(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.用戶手冊(cè)</b></p><p>　　本程序應(yīng)在Microsoft Visual C++ 6.0下運(yùn)行。NFA的確定化是編譯過程中一個(gè)重要的部分，由于本程序的

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

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

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

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

43、t;p>　　（4）王曉東編著.計(jì)算機(jī)算法設(shè)計(jì)與分析.電子工業(yè)出版社.2004</p><p><b>　　8. 附錄</b></p><p>　　NFA轉(zhuǎn)換為DFA采用C++編程實(shí)現(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é)點(diǎn)集合</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<<"請(qǐng)輸入NFA各邊信息,分別為 ：起點(diǎn) 條件[空為*] 終點(diǎn)，最后

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é)點(diǎn)中屬于終態(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)不在集合中，錯(cuò)誤！"<<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]); //對(duì)集合排序以便比較</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