編譯原理

詞法分析軟件學(xué)院網(wǎng)絡(luò)工程教研室萬仲保TEL：704682113907097766E-mail:zbwan@第四章詞法分析4.1詞法分析程序的設(shè)計4.2單詞的描述工具4.3有窮自動機(jī)4.4正規(guī)式和有窮自動機(jī)的等價性4.5正規(guī)文法和有窮自動機(jī)間的轉(zhuǎn)換詞法分析程序執(zhí)行詞法分析的程序稱為詞法分析程序或掃描程序。詞法分析程序的主要功能：讀入的源程序；輸出單詞符號。單詞是語言中具有獨立意義的最小單位，包括保留字、標(biāo)識符、運算符、標(biāo)點符號和常量等。詞法分析程序和語法分析程序的關(guān)系詞法分析程序的輸出詞法分析工作分離的意義詞法分析程序和語法分析程序的關(guān)系詞法分析程序的輸出單詞符號是一個程序設(shè)計語言的基本語法符號。單詞符號的分類單詞符號的一般輸出表達(dá)方式單詞符號的分類1、基本字（關(guān)鍵字）：如PASCAL語言中的begin,end,if,while,var等；2、標(biāo)識符：用來表示各種名字，如常量名、變量名和過程名等；3、常數(shù)（量）：各種類型的常數(shù)，如25，3.1415，TRUE和"ABC"等；4、運算符：如+-*/<<=等；5、界符：如逗號，分號，括號等。詞法分析程序所輸出的單詞符號常常采用以下二元式表示：(單詞種別，單詞自身的值)。單詞的種別是語法分析需要的信息，單詞自身的值則是編譯其它階段需要的信息。單詞符號的一般輸出表達(dá)方式詞法分析工作分離的意義使整個編譯程序的結(jié)構(gòu)更簡潔、清晰和條理化。詞法分析比語法分析簡單的多，但是由于源程序結(jié)構(gòu)上的一些細(xì)節(jié)，常使得識別單詞的工作甚為曲折和費時。例如，空白和注釋的處理；再比如對于FORTRAN那種受書寫格式限制的語言，需在識別單詞時進(jìn)行特殊處理等等。如果統(tǒng)統(tǒng)合在語法分析時一并考慮，顯然會使得分析程序的結(jié)構(gòu)復(fù)雜得多。

編譯程序的效率會改進(jìn)。大部分編譯時間是花費在掃描字符以把單詞符號分離出來。把詞法分析獨立出來，采用專門的讀字符和分離單詞的技術(shù)可大大加快編譯速度。另外，由于單詞的結(jié)構(gòu)可用有效的方法和工具進(jìn)行描述和識別，進(jìn)而可建立詞法分析程序的自動構(gòu)造工具。

增強(qiáng)編譯程序的可移植性。在同一個語言的不同實現(xiàn)中，或多或少地會涉及到與設(shè)備有關(guān)的特征，比如采用ASCII還是EBCDIC字符編碼。另外語言的字符集的特殊性的處理，一些專用符號，如PASCAL中的"↑"的表示等等，都可置于詞法分析程序中解決而不影響編譯程序其它成分的設(shè)計。單詞的描述工具程序設(shè)計語言中的單詞是基本語法符號。單詞符號的語法可以用有效的工具加以描述，并且基于這類描述工具，可以建立詞法分析技術(shù)，進(jìn)而可以建立詞法分析程序的自動構(gòu)造方法。正規(guī)文法正規(guī)式正規(guī)文法和正規(guī)式的轉(zhuǎn)換正規(guī)文法（正規(guī)文法）：設(shè)G=(VN，VT，P，S)，若P中的每一個產(chǎn)生式的形式都是A→aB或A→a，其中A和B都是非終結(jié)符，a是終結(jié)符。正規(guī)文法所描述的是VT*上的正規(guī)集。多數(shù)程序設(shè)計語言的單詞語法都可用正規(guī)文法來描述。正規(guī)式正規(guī)式也稱正則表達(dá)式，是表示正規(guī)集的數(shù)學(xué)工具。正規(guī)式和它所表示的正規(guī)集的遞歸定義：設(shè)字母表為Σ，輔助字母表Σ’={Φ，ε，|，·，*，(，)}。1、ε和Φ都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為{ε}和{}；2、任何a∈Σ，a是Σ上的一個正規(guī)式，它所表示的正規(guī)集為{a}；3、假定e1和e2都是Σ上的正規(guī)式，它們所表示的正規(guī)集分別為L(e1)和L(e2)，那么，(e1),e1|e2,e1·e2,e1*也都是正規(guī)式,它們所表示的正規(guī)集分別為L(e1),L(e1)∪L(e2),L(e1)L(e2)和(L(e1))*。4、僅由有限次使用上述三步驟而定義的表達(dá)式才是Σ上的正規(guī)式，僅由這些正規(guī)式所表示的字集才是Σ上的正規(guī)集。示例4.2示例4.3正規(guī)式的運算律令={a，b}，上的正規(guī)式和相應(yīng)的正規(guī)集的例子有：正規(guī)式 正規(guī)集a {a}ab {a,b}ab {ab}(ab)(ab) {aa,ab,ba,bb}a {,a,a,……任意個a的串}(ab) {,a,b,aa,ab……所有由a和b組成的串}(ab)(aabb)(ab) {上所有含有兩個相繼的a或兩個相繼的b組成的串}例4.2例4.3令Σ={d，·，ε，+，-},則Σ上的正規(guī)式d*(·dd*|ε)(ε(+|-ε|)dd*|ε)表示的是無符號數(shù)。其中d為0~9中的數(shù)字。正規(guī)式的運算律設(shè)r,s,t為正規(guī)式，正規(guī)式服從的代數(shù)規(guī)律有：1、rs=sr “或”滿足交換律2、r(st)=(rs)t“或”的可結(jié)合律3、(rs)t=r(st) “連接”的可結(jié)合律4、r(st)=rsrt 分配律(st)r=srtr 5、r=r,r=r 是“連接”的恒等元素正規(guī)文法和正規(guī)式的轉(zhuǎn)換正規(guī)式轉(zhuǎn)換為正規(guī)文法的規(guī)則正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則正規(guī)式轉(zhuǎn)換為正規(guī)文法的規(guī)則將上的一個正軌式轉(zhuǎn)換為文法G=(VN，VT，P，S)，令VT=

確定文法的產(chǎn)生式和的VN規(guī)則為：選擇識別符號S的生成產(chǎn)生式Sr；若x,y都是正規(guī)式，對形如Axy的產(chǎn)生式，可重寫為AxBBy（BVN）

對已轉(zhuǎn)換的文法中的形如Axy的產(chǎn)生式，可重寫為：AxBAyBxBBy（BVN）對形如Axy的產(chǎn)生式，可重寫為：AxAy

不斷應(yīng)用上述規(guī)則做變換，直到每個產(chǎn)生式最多含一個終結(jié)符為止。示例：例4.4例4.4將R=a(ad)轉(zhuǎn)換成相應(yīng)的正規(guī)文法。解：令S為文法的開始符號，首先形成Sa(ad)，然后形成SaA和A(ad)，再重寫第二條產(chǎn)生式形成SaAA(ad)BAB(ad)BB進(jìn)而變換為SaAAaBAdBABaBBdBB正規(guī)文法轉(zhuǎn)換為正規(guī)式的規(guī)則規(guī)則文法產(chǎn)生式正規(guī)式1AxBByr=xy2AxA|yr=xy3AxAyr=xy示例：例4.5例4.5G[s]:SaA

AaA AdA

Sa

Aa

AdS=aAa

A=(aAdA)(ad)

=(ad)(ad)將A右端代入S的正規(guī)式得：

S=a(ad)(ad)a利用正規(guī)式的運算律，可得：

S=a((ad)(ad))

=a(ad)

R=a(ad)4.3有窮自動機(jī)有窮自動機(jī)(也稱有限自動機(jī))作為一種識別裝置，它能準(zhǔn)確地識別正規(guī)集，即識別正規(guī)文法所定義的語言和正規(guī)式所表示的集合。有窮自動機(jī)分類:確定的有窮自動機(jī)（DFA）不確定的有窮自動機(jī)（NFA）NFADFA的轉(zhuǎn)換DFA的化簡確定的有窮自動機(jī)(DeterministicFiniteAutomata)定義示例：例4.6DFA的表示方式：狀態(tài)轉(zhuǎn)換圖狀態(tài)矩陣相關(guān)的定義符號串在自動機(jī)上接受符號串在自動機(jī)上運行正規(guī)式與DFA之間的關(guān)系DFA定義一個確定的有窮自動機(jī)（DFA）M是一個五元組：M=（K，Σ，f，S，Z）其中：1、K是一個有窮集，它的每個元素稱為一個狀態(tài)；2、Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號字母表；3、f是轉(zhuǎn)換函數(shù)，是在K×Σ→K上的映射，即，如f（ki，a）=kj，（ki∈K，kj∈K）就意味著，當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；4、S∈K是唯一的一個初態(tài)；5、ZK是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。DFA例：例4.6DFAM=（{S,U,V,Q},{a,b},f,S,{Q}）其中f定義為：f（S，a）=U f（V，a）=Uf（S，b）=V f（V,b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q狀態(tài)轉(zhuǎn)換圖一個DFA可以表示成一個狀態(tài)圖(或稱狀態(tài)轉(zhuǎn)換圖)。假定DFAM含有m個狀態(tài)，n個輸入字符，那么這個狀態(tài)圖含有m個結(jié)點，每個結(jié)點最多有n個弧射出，整個圖含有唯一一個初態(tài)結(jié)點和若干個終態(tài)結(jié)點，初態(tài)結(jié)點冠以雙箭頭“=>”或標(biāo)以“-”，終態(tài)結(jié)點用雙圈表示或標(biāo)以“+”，若f(ki,a)=kj，則從狀態(tài)結(jié)點ki到狀態(tài)結(jié)點kj畫標(biāo)記為a的弧。示例DFA的狀態(tài)圖表示f（S，a）=U f（V，a）=Uf（S，b）=V f（V,b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=QbSUVQaaaba，bb狀態(tài)矩陣一個DFA還可以用一個矩陣表示，該矩陣的行表示狀態(tài)，列表示輸入字符，矩陣元素表示相應(yīng)狀態(tài)行和輸入字符列下的新狀態(tài)，即k行a列為f(k,a)的值。用雙箭頭"=>"標(biāo)明初態(tài)；否則第一行即是初態(tài)，相應(yīng)終態(tài)行在表的右端標(biāo)以1，非終態(tài)標(biāo)以0。示例DFA的矩陣表示f（S，a）=U f（V，a）=Uf（S，b）=V f（V，b）=Qf（U，a）=Q f（Q，a）=Qf（U，b）=V f（Q，b）=Q字符狀態(tài)0100符號串在自動機(jī)上被接受對于∑*中的任何字符串t，若存在一條從初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條路上所有弧的的標(biāo)記符連接成的字符串等于t，則稱t可為DFAM所接受，若M的初態(tài)結(jié)同時又是終態(tài)結(jié)，則空字可為M所接受（識別）。若t∑*，f(S，t)=P，其中S為DFA

M的開始狀態(tài)，PZ，Z為終態(tài)集。則稱t為DFAM所接受（識別）。一個輸入符號串t，（我們將它表示成t1tx的形式，其中t1∈∑，tx∈∑*）在DFAM上運行的定義為：f（Q，t1tx）=f（f（Q，t1），tx）

其中Q∈K擴(kuò)充轉(zhuǎn)換函數(shù)f，是K×Σ*→K上的映射，且：

f（Q，）=Q符號串在自動機(jī)上運行正規(guī)式與DFA之間的關(guān)系∑上一個符號串集V∑*是正規(guī)的，當(dāng)且僅當(dāng)存在一個∑上的確定有窮自動機(jī)M，使得V=L(M)。示例：證明t=baab被例4.6的DFA所接受.證明：

f（S，baab）

=f（f（S，b），aab）

=f（V，aab）

=f（f（V，a），ab）

=f（U，ab）

=f（f（U，a），b）

=f（Q，b）

=QQ屬于終態(tài)。得證。bSUVQaaaba，bb不確定的有窮自動機(jī)NFA定義不確定的有窮自動機(jī)NFAN=(K，∑，f，S，Z)，其中：

K是一個有窮集，它的每個元素稱為一個狀態(tài)；Σ是一個有窮字母表，它的每個元素稱為一個輸入符號；f為從K×∑*到K的子集的映射；SK是初始狀態(tài)集；ZK為終止?fàn)顟B(tài)集。示例：例4.7字符串在NFA上的識別NFA和DFA的等價性例4.7一個NFAM=（{0，1，2，3，4}，{a，b}，f，{0}，{2，4}），其中

f（0，a）={0，3}f（0，b）={0，1}f（1，b）={2}f（2，a）={2}f（2，b）={2}f（3，a）={4}f（4，a）={4}f（4，b）={4}狀態(tài)轉(zhuǎn)換圖如右圖所示。b0314aaba，b2a，b

a，b若t∈∑*，f(S，t)=P，其中S為N的開始狀態(tài)，P∈Z，Z為終態(tài)集。則稱t為NFAN所接受（識別）。對于Σ*中的任何一個串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱t可為NFAM所識別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個初態(tài)結(jié)到某個終態(tài)結(jié)的ε道路，那么空字可為M所接受。字符串在NFA上的識別NFA和DFA的等價性對于每一個NFAM，存在一個DFAM′，使得L（M）=L（M′）。對于任何兩個有窮自動機(jī)M和M′，如果L（M）=L（M′），則稱M和M′是等價的。NFADFA的轉(zhuǎn)換——NFA的確定化NFA確定化定理：設(shè)L為一個由不確定的有窮自動機(jī)接受的集合，則存在一個接受L的確定的自動機(jī)L(M)=L(M')。狀態(tài)集合I的運算定義NFA確定化狀態(tài)集合I的運算定義狀態(tài)集合I的-閉包，表示為-closure(I)，定義為一狀態(tài)集，是狀態(tài)集I中的任何狀態(tài)S經(jīng)任意條弧而能到達(dá)的狀態(tài)的集合。狀態(tài)集合I的任何狀態(tài)S都屬于-closure(I)。狀態(tài)集合I的a弧轉(zhuǎn)換，表示為move(I,a)定義為狀態(tài)集合J，其中J是所有那些可從I的某一狀態(tài)經(jīng)過一條a弧而到達(dá)的狀態(tài)的全體。示例轉(zhuǎn)換的計算：對于自動機(jī)M=(K,∑,f,K0,Kt)，設(shè)I={s1,s2,,sj}，a是∑中的一個元素，則move(I,a)=f(s1,a)∪f(s2,a)∪

∪f(sj,a)

狀態(tài)集合I的運算示例

-closure(0)={0,1,2,4,7}即{0,1,2,4,7}中的任一狀態(tài)都是從狀態(tài)0經(jīng)任意條弧可到達(dá)的狀態(tài)，令A(yù)={0,1,2,4,7},則move(A,a)={3,8}，因為在狀態(tài)0,1,2,4,7中，只有狀態(tài)2和7有a弧射出，分別到達(dá)狀態(tài)3和8。-closure(3,8)={1,2,3,4,6,7,8}b124ab10a

0356789b返回例4.8a返回例4.8bNFA確定化NFA確定為DFA的構(gòu)造方法構(gòu)造NFA的狀態(tài)K的子集的算法示例：示例一：對NFAN構(gòu)造其子集——例4.8a示例二：對NFAN確定化——例4.8bNFA確定為DFA的構(gòu)造方法假設(shè)NFAN=(K,,f,K0,Kt)按如下辦法構(gòu)造一個DFAM=(S,,d,S0,St)，使得L(M)=L(N)：1.M的狀態(tài)集S由K的一些子集組成。用[S1S2...

Sj]表示S的元素，其中S1,S2,,...

Sj是K的狀態(tài)。并且約定，狀態(tài)S1,S2,,...

Sj是按某種規(guī)則排列的，即對于子集{S1,S2}={S2,S1,}來說，S的狀態(tài)就是[S1S2]；2.M和N的輸入字母表是相同的，即是；3.轉(zhuǎn)換函數(shù)是這樣定義的：

D([S1,S2,...

,

Sj],a)=[R1,

R2,...

,

Rt]

其中

-closure(move([S1,S2,...

,

Sj],a))=[R1,

R2,...

,

Rt]4.S0=-closure(K0)為M的開始狀態(tài)；5.St={[Si,Sk,...,Se]，其中[Si,Sk,...,Se]S且{Si

,Sk,,...

Se}∩Kt}構(gòu)造NFAN的狀態(tài)K的子集的算法假定所構(gòu)造的子集族為C,即C=(T1,T2,,...

Ti),其中T1,T2,,...

Ti為狀態(tài)K的子集。1.開始，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。2.while（C中存在尚未被標(biāo)記的子集T）do{標(biāo)記T；for每個輸入字母ado{U:=-closure(move(T,a))；ifU不在C中then

將U作為未標(biāo)記的子集加在C中}}例4.8aNFAN的狀態(tài)轉(zhuǎn)換圖構(gòu)造子集的步驟：首先計算ε-closure(0)，令T0=ε-closure(0)={0,1,2,4,7}，T0未被標(biāo)記，它現(xiàn)在是子集族C的唯一成員。標(biāo)記T0；令T1=ε-closure(move(T0,a))={1,2,3,4,6,7,8}，將T1加入C中，T1未被標(biāo)記。

令T2=ε-closure(move(T0,b))={1,2,4,5,6,7}，將T2加入C中，它未被標(biāo)記。標(biāo)記T1；計算ε-closure(move(T1,a))，結(jié)果為{1,2,3,4,6,7,8}，即T1，T1已在C中。

計算ε-closure(move(T1,b))，結(jié)果為{1,2,4,5,6,7,9}，令其為T3，T3加至C中，它未被標(biāo)記。標(biāo)記T2，計算ε-closure(move(T2,a))，結(jié)果為{1,2,3,4,6,7,8}，即T1，T1已在C中。

計算ε-closure(move(T2,b))，結(jié)果為{1,2,4,5,6,7}，即T2，T2已在C中。標(biāo)記T3，計算ε-closure(move(T3,a))，結(jié)果為{1,2,3,4,6,7,8}，即T1。

計算ε-closure(move(T3,b))，結(jié)果為{1,2,4,5,6,7,10}，令其為T4，加入C中，T4未被標(biāo)記。標(biāo)記T4，計算ε-closure(move(T4,a))，結(jié)果為{1,2,3,4,6,7,8}，即T1

計算ε-closure(move(T4,b))結(jié)果為{1,2,4,5,6,7}，即T2。至此，算法終止共構(gòu)造了五個子集：T0={0,1,2,4,7}T1={1,2,3,4,6,7,8}T2={1,2,4,5,6,7}T3={1,2,4,5,6,7,9}T4={1,2,4,5,6,7,10}例4.8bNFAN的狀態(tài)轉(zhuǎn)換圖確定化：構(gòu)造子集、確定構(gòu)造的DFAM；作出狀態(tài)轉(zhuǎn)換圖。確定構(gòu)造的DFAMNFAN構(gòu)造的DFAM為

S={[T0]，[T1]，[T2]，[T3]，[T4]}Σ={a,b}D([T0]，a)=[T1]D([T2]，a)=[T1]D([T0]，b)=[T2]D([T2]，b)=[T2]D([T1]，a)=[T1]D([T3]，a)=[T1]D([T1]，b)=[T3]D([T3]，b)=[T4]D([T4],a)=[T1]D([T4]，b)=[T2]S0=[T0]St=[T4]不妨將[T0]，[T1]，[T2]，[T3]，[T4]重新命名，以利于書寫，或用A，B，C，D，E或用0，1，2，3，4分別表示。作出狀態(tài)轉(zhuǎn)換圖DFA的最小化（化簡）最小狀態(tài)DFA沒有多余狀態(tài)(死狀態(tài))：指這樣的狀態(tài)，從該自動機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個狀態(tài)。沒有兩個狀態(tài)是互相等價（不可區(qū)別）。多余狀態(tài)消除示例狀態(tài)可區(qū)別的示例兩個狀態(tài)s和t等價：滿足一致性條件——狀態(tài)s和t必須同時為可接受狀態(tài)或不可接受狀態(tài)。蔓延性條件——對于所有輸入符號，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價的狀態(tài)里。如果有窮自動機(jī)的狀態(tài)s和t不等價，則稱這兩個狀態(tài)是可區(qū)別的。DFA的最小化方法——分割法DFA最小化實例消除多余狀態(tài)示例s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s6010

1

1

0

0

0

1

1

0s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s5s6

s3s1

s8s0

s0s1

s3s6010

1

1

0

0

0

1

1

0s0

s1

s2

s3

s4

s5

s6

s7

s8s1s5

s2s7

s2s5

s5s7

s3s1

s0s1010

1

1

0

0

1s0

s1

s2

s3

s5

s7(a)(b)(c)從狀態(tài)矩陣（a）可知，狀態(tài)s4、s6、s8不可以從s0出發(fā)，經(jīng)過任何輸入串到達(dá)的狀態(tài)，因此，可以將其狀態(tài)連同射出的弧一并消除。其中（b）為過程，（c）為消除后的狀態(tài)矩陣。狀態(tài)可區(qū)別的示例如下圖所示。狀態(tài)0和4是可區(qū)別的。因為狀態(tài)4是可接受態(tài)(終態(tài))，而0是不可接受態(tài)。狀態(tài)2和3是可區(qū)別的，因為讀入b后分別到達(dá)2和4，而2和4不是等價的。b02134abaaaabbbDFA的最小化方法DFA的最小化

對于一個DFAM=（K,∑,f,k0,kt)，存在一個最小狀態(tài)DFAM’=（K’,∑,f’,k0’,kt’)，使L(M’)=L(M)。算法的核心是把M的狀態(tài)集K分成不相交的子集。結(jié)論：接受L的最小狀態(tài)有窮自動機(jī)不計同構(gòu)是唯一的。分割法算法分割法算法1．首先，將M的狀態(tài)集K按終態(tài)與非終態(tài)劃分為兩個子集Z及K-Z，以構(gòu)成初始分別，記為π＝(z，K-z)。2．設(shè)當(dāng)前的分劃π中已含有m個子集，即π＝{I1,I2,…,Im}，其中，屬于不同子集的狀態(tài)是可區(qū)分的，而屬于同一子集中的諸狀態(tài)則是待區(qū)分的。即需對每一子集Ii={Si1,Si2,…,Sim}中各狀態(tài)Sir(SirK,1≤r≤n)進(jìn)行考察，看是否還能對它們再進(jìn)行區(qū)分。例如，Sip和Siq是Ii中的兩個狀態(tài)，若有某個a∑，使f(Sip,a)＝Sju及f(Siq，a)＝Skv，而狀態(tài)Sju及Skv分別屬于π中兩個不同的子集Ij和Ik，故Sju和Skv為某一w所區(qū)分，從而Sju和Skv必為w所區(qū)分，故應(yīng)將子集Ii進(jìn)一步劃分，使Sip和Siq分別屬于Ii的不同的子集。也就是說，對于每一子集Ii及每一a∑，需考察；Iia＝f(Ii，a)＝Uf(Sir，a)。若Iia中的狀態(tài)分別落于π中的p個不同的子集，則將Ii分為p個更小的狀態(tài)子集Ii(1),Ii(2),…,Ii(p)，使得對于每一個Ii(j)，f(Ii(j)，a)中的全部狀態(tài)都落于π的同一子集之中。注意，若對某狀態(tài)Sir，f

(Sir，a)無意義，則Sir與任何Sir(f(Sir，a)有定義)都是可區(qū)分的。這樣，每細(xì)分一次，就得一個新的分劃πnew，且分劃中的子集數(shù)也由原來的m個變?yōu)閙+p-1個。分割法算法(2)3．若πnew≠π，則將πnew作為π再重復(fù)第二步中的過程，如此等等，直到最后得到一個分劃π，使πnew=π，即π中的各個子集不能再劃分為止。4．對于所得的最后分劃π，從它的每一子集Ij={Sj1,Sj2,…,Sjm}中任選一個狀態(tài)，比方說Sj1，作為Ij中所含各狀態(tài)的代表，這些所選出的狀態(tài)便組成了M’的狀態(tài)集K’。而且，若Ij中含有M的初態(tài)，則Sj1為M‘的初態(tài)；若Ij中合有M的終態(tài)，則Sj1為M’的一個終態(tài)。此外，為構(gòu)成DFAM’，還應(yīng)將各子集中落選的狀態(tài)從原DFAM中則去，并將原來進(jìn)入這些狀態(tài)的所有矢線都改為進(jìn)入它們的代表狀態(tài)。例4.9將右上圖所示的DFAM最小化。解：首先將M的狀態(tài)分成兩個子集：一個由終態(tài)(可接受態(tài))組成，一個由非終態(tài)組成，這個初始劃分P0為：P0=({1，2，3，4}，{5，6，7})，顯然第一個子集中的任何狀態(tài)都與第二個子集中的任何狀態(tài)不等價。

現(xiàn)在觀察第一個子集{1，2，3，4}，在讀入輸入符號a后，狀態(tài)3和4分別轉(zhuǎn)換為第一個子集中所含的狀態(tài)1和4，而1和2分別轉(zhuǎn)換為第二個子集中所含的狀態(tài)6和7，這就意味著{1，2}中的狀態(tài)和{3，4}中的任何狀態(tài)在讀入a后到達(dá)了不等價的狀態(tài)，因此{(lán)1，2}中的任何狀態(tài)與{3，4}中的任何狀態(tài)都是可區(qū)別的，因此得到了新的劃分P1如下：

P1=({1，2}{3，4}{5，6，7})

下面試圖在P1中尋找一個子集和一個輸入符號使得這個子集中的狀態(tài)可區(qū)別，P1中的子集{3，4}對應(yīng)輸入符號a將再分割，而得到劃分P2=({1，2}，{3}，{4}，{5，6，7})。

P2中的{5，6，7}可由輸入符號a或b而分割，得到劃分P3=({1，2}，{3}，{4}，{5}，{6，7})。

經(jīng)過考察，P3不能再劃分了。令1代表{1，2}消去2，令6代表{6，7}，消去7，便得到了右下圖所示的DFAM′，它是所求最小化的DFAM。正規(guī)式和有窮自動機(jī)的等價性正規(guī)式和有窮自動機(jī)的等價性說明：1.

對于∑上的NFAM，可以構(gòu)造一個∑上的正規(guī)式R，使得

L(R)=L(M)。2.對于∑上的一個正規(guī)式R，可以構(gòu)造一個∑上的NFAM，使得L(M)=L(R)。由NFAM求解正規(guī)式的方法由正規(guī)式構(gòu)造NFAM的方法構(gòu)造NFA的形式描述由NFAM求解正規(guī)式的方法1、在M的狀態(tài)轉(zhuǎn)換圖上加進(jìn)二個結(jié)點，記為x、y。其中x結(jié)點用弧與M的所有初態(tài)結(jié)點連接，將M的所有終態(tài)結(jié)點用弧與y結(jié)點連接，組成一個等價M，且M’只有x為初態(tài)，y為終態(tài)。2、運用消結(jié)規(guī)則逐步消去M’中除x、y之外的所有結(jié)點，最后得到的x、y兩個結(jié)點間弧上的標(biāo)記即為NFA相應(yīng)的正規(guī)式。消除拓廣狀態(tài)轉(zhuǎn)換圖結(jié)點的規(guī)則示例：例4.10消除拓廣狀態(tài)轉(zhuǎn)換圖結(jié)點的規(guī)則例4.10b0314aaba，b2a，b

a，b由正規(guī)式構(gòu)造NFAM的方法單一的正規(guī)式，相應(yīng)的NFA構(gòu)造規(guī)則：對于正規(guī)式，所構(gòu)造的NFA為；對于正規(guī)式ε，所構(gòu)造的NFA為；對于正規(guī)式a，a∈Σ，所構(gòu)造的NFA為。組合的正規(guī)式，若s，t為Σ上的正規(guī)式，相應(yīng)的NFA構(gòu)造規(guī)則：對正規(guī)式R=s|t，所構(gòu)造的NFA(R)為；對正規(guī)式R=st，所構(gòu)造的NFA(R)為；對于正規(guī)式R=s*，所構(gòu)造的NFA(R)為；正規(guī)式(s)的NFA同s的NFA一樣。示例：例4.11

例4.11a正規(guī)式所構(gòu)造的NFA正規(guī)式ε所構(gòu)造的NFA正規(guī)式a(a∈Σ)所構(gòu)造的NFA正規(guī)式R=s|t所構(gòu)造的NFA(R)其中x是NFA(R)的初態(tài)，y是NFA(R)的終態(tài)，x到N(s)和N(t)的初態(tài)各有一ε弧，從N(s)和N(t)的終態(tài)各有一ε弧到y(tǒng)，現(xiàn)在N(s)和N(t)的初態(tài)或終態(tài)已不作為N(R)的初態(tài)和終態(tài)了。正規(guī)式R=st所構(gòu)造的NFA(R)其中N(s)的初態(tài)成了N(R)的初態(tài)，N(t)的終態(tài)成了N(R)的終態(tài)。N(s)的終態(tài)與N(t)的初態(tài)合并為N(R)的一個既不是初態(tài)也不是終態(tài)的狀態(tài)。正規(guī)式R=s*所構(gòu)造的NFA(R)這里x和y分別是NFA(R)的初態(tài)和終態(tài)，從x引ε弧到N(s)的初態(tài)，從N(s)的終態(tài)引ε弧到y(tǒng)，從x到y(tǒng)引ε弧，同樣N(s)的終態(tài)可沿ε弧的邊直接回到N(s)的初態(tài)。N(s)的初態(tài)或終態(tài)不再是N(s)的初態(tài)和終態(tài)。例4.11為R=(a|b)*abb構(gòu)造NFAN，使得L(N)=L(R)。解：從左到右分解R，令r1=a，第一個a，則其NFA的狀態(tài)轉(zhuǎn)換圖如下：令r2=b，則其NFA的狀態(tài)轉(zhuǎn)換圖如下：例4.11令r3=r1|r21，則其NFA的狀態(tài)轉(zhuǎn)換圖如下：令r4=r3'，則其NFA的狀態(tài)轉(zhuǎn)換圖如下：例