編譯原理第04章 詞法分析

編譯原理

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

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

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

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

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

不斷應(yīng)用上述規(guī)則做變換，直到每個(gè)產(chǎn)生式最多含一個(gè)終結(jié)符為止。示例：例4.4例4.4將R=a(ad)轉(zhuǎn)換成相應(yīng)的正規(guī)文法。解：令S為文法的開(kāi)始符號(hào)，首先形成Sa(ad)，然后形成SaA和A(ad)，再重寫(xiě)第二條產(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ī)式的運(yùn)算律，可得：

S=a((ad)(ad))

=a(ad)

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

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

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

f（Q，）=Q符號(hào)串在自動(dòng)機(jī)上運(yùn)行正規(guī)式與DFA之間的關(guān)系∑上一個(gè)符號(hào)串集V∑*是正規(guī)的，當(dāng)且僅當(dāng)存在一個(gè)∑上的確定有窮自動(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不確定的有窮自動(dòng)機(jī)NFA定義不確定的有窮自動(dòng)機(jī)NFAN=(K，∑，f，S，Z)，其中：

K是一個(gè)有窮集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；Σ是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)；f為從K×∑*到K的子集的映射；SK是初始狀態(tài)集；ZK為終止?fàn)顟B(tài)集。示例：例4.7字符串在NFA上的識(shí)別NFA和DFA的等價(jià)性例4.7一個(gè)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的開(kāi)始狀態(tài)，P∈Z，Z為終態(tài)集。則稱(chēng)t為NFAN所接受（識(shí)別）。對(duì)于Σ*中的任何一個(gè)串t，若存在一條從某一初態(tài)結(jié)到某一終態(tài)結(jié)的道路，且這條道路上所有弧的標(biāo)記字依序連接成的串(不理采那些標(biāo)記為ε的弧)等于t，則稱(chēng)t可為NFAM所識(shí)別(讀出或接受)。若M的某些結(jié)既是初態(tài)結(jié)又是終態(tài)結(jié)，或者存在一條從某個(gè)初態(tài)結(jié)到某個(gè)終態(tài)結(jié)的ε道路，那么空字可為M所接受。字符串在NFA上的識(shí)別NFA和DFA的等價(jià)性對(duì)于每一個(gè)NFAM，存在一個(gè)DFAM′，使得L（M）=L（M′）。對(duì)于任何兩個(gè)有窮自動(dòng)機(jī)M和M′，如果L（M）=L（M′），則稱(chēng)M和M′是等價(jià)的。NFADFA的轉(zhuǎn)換——NFA的確定化NFA確定化定理：設(shè)L為一個(gè)由不確定的有窮自動(dòng)機(jī)接受的集合，則存在一個(gè)接受L的確定的自動(dòng)機(jī)L(M)=L(M')。狀態(tài)集合I的運(yùn)算定義NFA確定化狀態(tài)集合I的運(yùn)算定義狀態(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)過(guò)一條a弧而到達(dá)的狀態(tài)的全體。示例轉(zhuǎn)換的計(jì)算：對(duì)于自動(dòng)機(jī)M=(K,∑,f,K0,Kt)，設(shè)I={s1,s2,,sj}，a是∑中的一個(gè)元素，則move(I,a)=f(s1,a)∪f(wàn)(s2,a)∪

∪f(wàn)(sj,a)

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

-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}，因?yàn)樵跔顟B(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的子集的算法示例：示例一：對(duì)NFAN構(gòu)造其子集——例4.8a示例二：對(duì)NFAN確定化——例4.8bNFA確定為DFA的構(gòu)造方法假設(shè)NFAN=(K,,f,K0,Kt)按如下辦法構(gòu)造一個(gè)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ī)則排列的，即對(duì)于子集{S1,S2}={S2,S1,}來(lái)說(shuō)，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的開(kāi)始狀態(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.開(kāi)始，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。2.while（C中存在尚未被標(biāo)記的子集T）do{標(biāo)記T；for每個(gè)輸入字母ado{U:=-closure(move(T,a))；ifU不在C中then

將U作為未標(biāo)記的子集加在C中}}例4.8aNFAN的狀態(tài)轉(zhuǎn)換圖構(gòu)造子集的步驟：首先計(jì)算ε-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；計(jì)算ε-closure(move(T1,a))，結(jié)果為{1,2,3,4,6,7,8}，即T1，T1已在C中。

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

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

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

計(jì)算ε-closure(move(T4,b))結(jié)果為{1,2,4,5,6,7}，即T2。至此，算法終止共構(gòu)造了五個(gè)子集：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]重新命名，以利于書(shū)寫(xiě)，或用A，B，C，D，E或用0，1，2，3，4分別表示。作出狀態(tài)轉(zhuǎn)換圖DFA的最小化（化簡(jiǎn)）最小狀態(tài)DFA沒(méi)有多余狀態(tài)(死狀態(tài))：指這樣的狀態(tài)，從該自動(dòng)機(jī)的開(kāi)始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)。沒(méi)有兩個(gè)狀態(tài)是互相等價(jià)（不可區(qū)別）。多余狀態(tài)消除示例狀態(tài)可區(qū)別的示例兩個(gè)狀態(tài)s和t等價(jià)：滿(mǎn)足一致性條件——狀態(tài)s和t必須同時(shí)為可接受狀態(tài)或不可接受狀態(tài)。蔓延性條件——對(duì)于所有輸入符號(hào)，狀態(tài)s和狀態(tài)t必須轉(zhuǎn)換到等價(jià)的狀態(tài)里。如果有窮自動(dòng)機(jī)的狀態(tài)s和t不等價(jià)，則稱(chēng)這兩個(gè)狀態(tài)是可區(qū)別的。DFA的最小化方法——分割法DFA最小化實(shí)例消除多余狀態(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)過(guò)任何輸入串到達(dá)的狀態(tài)，因此，可以將其狀態(tài)連同射出的弧一并消除。其中（b）為過(guò)程，（c）為消除后的狀態(tài)矩陣。狀態(tài)可區(qū)別的示例如下圖所示。狀態(tài)0和4是可區(qū)別的。因?yàn)闋顟B(tài)4是可接受態(tài)(終態(tài))，而0是不可接受態(tài)。狀態(tài)2和3是可區(qū)別的，因?yàn)樽x入b后分別到達(dá)2和4，而2和4不是等價(jià)的。b02134abaaaabbbDFA的最小化方法DFA的最小化

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

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

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

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

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

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

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

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

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

a，b由正規(guī)式構(gòu)造NFAM的方法單一的正規(guī)式，相應(yīng)的NFA構(gòu)造規(guī)則：對(duì)于正規(guī)式，所構(gòu)造的NFA為；對(duì)于正規(guī)式ε，所構(gòu)造的NFA為；對(duì)于正規(guī)式a，a∈Σ，所構(gòu)造的NFA為。組合的正規(guī)式，若s，t為Σ上的正規(guī)式，相應(yīng)的NFA構(gòu)造規(guī)則：對(duì)正規(guī)式R=s|t，所構(gòu)造的NFA(R)為；對(duì)正規(guī)式R=st，所構(gòu)造的NFA(R)為；對(duì)于正規(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)的一個(gè)既不是初態(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，第一個(gè)a，則其N(xiāo)FA的狀態(tài)轉(zhuǎn)換圖如下：令r2=b，則其N(xiāo)FA的狀態(tài)轉(zhuǎn)換圖如下：例4.11令r3=r1|r21，則其N(xiāo)FA的狀態(tài)轉(zhuǎn)換圖如下：令r4=r3'，則其N(xiāo)FA的狀態(tài)轉(zhuǎn)換圖如下：例