24-正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造課件

編譯原理

PrincipleofCompiling郭一晶

廈門大學(xué)嘉庚學(xué)院6/3/202312.4正規(guī)表達(dá)式到有限自動(dòng)機(jī)的構(gòu)造2.4.1由正規(guī)式構(gòu)造等價(jià)的NFAM2.4.2NFAM的確定化2.4.3DFAM的化簡(jiǎn)2.4.4正規(guī)式到有限自動(dòng)機(jī)構(gòu)造示例2.4.5從NFAM到正規(guī)表達(dá)式的轉(zhuǎn)換6/3/20232有限自動(dòng)機(jī)和正規(guī)表達(dá)式的等價(jià)性：1.對(duì)于∑上的一個(gè)NFAM，可以構(gòu)造一個(gè)∑上的正規(guī)式R,使得L(R)=L(M)。2.對(duì)于∑上的一個(gè)正規(guī)式R，可以構(gòu)造一個(gè)∑上的NFAM，使得L(M)=L(R)。注意：與某一NFA等價(jià)的DFA不一定唯一。6/3/202332.4正規(guī)式到有限自動(dòng)機(jī)的構(gòu)造2.4.1由正規(guī)式構(gòu)造等價(jià)的NFAM

由正規(guī)式構(gòu)造等價(jià)的NFAM的方法(Thompson構(gòu)造法)：

(1)將正規(guī)式R表示為拓廣轉(zhuǎn)換圖。X2YR6/3/20234(2)采用下述三條轉(zhuǎn)換規(guī)則構(gòu)造NFA

M。sisisjr1|r21.r1r2ee2.3.sjsjsisir1r2sisi*r1r1r1r2sjsjsjsksk6/3/20235對(duì)于正規(guī)式R,首先將其表示為拓廣轉(zhuǎn)換圖,其中X為初態(tài),Y為終態(tài),然后逐步運(yùn)用三條轉(zhuǎn)換規(guī)則不斷加入新結(jié)點(diǎn),直至每條有向邊上僅標(biāo)識(shí)Σ的一個(gè)字母或ε為止,至此NFAM構(gòu)造完成。例2.6

構(gòu)造b*(d|ad)(b|ab)+對(duì)應(yīng)的NFA。解:首先用R+=RR*把正規(guī)式改造為

b*(d|ad)(b|ab)(b|ab)*

然后構(gòu)造其NFAM，如下圖所示：6/3/20236b*(d|ad)(b|ab)(b|ab)*XY(b|ab)*d|adb*b|ababadεεbεεdb|abb41235εεbX41d26εεbb3578adbaabXX132YYY6/3/20237Thompson方法構(gòu)造的NFA有下列性質(zhì)：只有一個(gè)開始狀態(tài)和一個(gè)接受狀態(tài)，接受狀態(tài)沒有向外的轉(zhuǎn)換。的轉(zhuǎn)換規(guī)則可不可以改為？*r1sisjeer1例：(11+)*6/3/202382.4.2NFAM的確定化－－子集構(gòu)造法(SubsetConstruction)首先

定義FAM的任一狀態(tài)子集I的

_CLOSURE(I)：

(1)若si∈I,則si∈_CLOSURE(I)；

(2)若si∈I,則從si

出發(fā)經(jīng)過所能到達(dá)的 狀態(tài)sj

屬于_CLOSURE(I)。其次

定義Ia：

對(duì)FAM的任一狀態(tài)子集I,若a是Σ中的一個(gè)字符，則定義

Ia=_CLOSURE(J)，

其中J是從I中某一狀態(tài)出發(fā)經(jīng)過a所能到達(dá)的所有狀態(tài)的集合。J＝move(I,a)6/3/20239例2.7

對(duì)下圖,取I=_CLOSURE{1}={1,2},

求從狀態(tài)I出發(fā)經(jīng)一條有向邊a所能到達(dá)的狀態(tài)集J和_CLOSURE(J)。a1524ae6378eeaeeJ={5,3,4}_CLOSURE(J)={5,6,2,3,8,4,7}6/3/202310用子集法對(duì)NFA確定化的方法：(1)構(gòu)造一張轉(zhuǎn)換表,該表的第1列為狀態(tài)子集I,不同輸入符a

對(duì)應(yīng)表中一列Ia。(2)表的首行首列為_CLOSURE(s0)。(3)根據(jù)首行首列中的狀態(tài)集,為每個(gè)輸入符a求其Ia并記入相應(yīng)的Ia列中。若此Ia不同于第1列已存在的所有狀態(tài)子集,則將其順序列入空行中的第1列。(4)重復(fù)(3)直至對(duì)每個(gè)I及a均已求得Ia,且

無新的狀態(tài)子集Ia加入第1列為止。(5)重命名第1列的每個(gè)狀態(tài)集,所得狀態(tài)轉(zhuǎn)換矩陣即為與NFAM等價(jià)的DFAM'。6/3/202311例2.8

正規(guī)式(a|b)*(aa|bb)(a|b)*的NFAM如下:

試將其確定化為DFAM'。34251X6eeabababeeab2Y6/3/202312解:用子集法將上述NFAM確定化為

IIaIb{X,1,2}{1,2,3}{1,2,4}{1,2,3}{1,2,3,5,6,Y}{1,2,4}{1,2,4}{1,2,3}{1,2,4,5,6,Y}{1,2,3,5,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,4,6,Y}{1,2,3,6,Y}{1,2,4,5,6,Y}{1,2,3,6,Y}{1,2,3,5,6,Y}{1,2,4,6,Y}6/3/202313Sab012132214335464564635重命名為:6/3/202314a23252426120abbaababbaabb于是得到對(duì)應(yīng)的DFA如下：6/3/202315注意：如果DFA的某個(gè)狀態(tài)至少包含NFA的一個(gè)接受狀態(tài)，那么，這個(gè)狀態(tài)是DFA的一個(gè)接受狀態(tài)。DFA的一個(gè)狀態(tài)是NFA的一個(gè)狀態(tài)集合。

讀了輸入a1a2…an后，NFA能到達(dá)的所有狀態(tài)：s1,s2,…,

sk，則DFA到達(dá)狀態(tài){s1,s2,…,

sk}。6/3/202316算法描述：1開始，假定所構(gòu)造的子集族為C，令-closure(K0)為C中唯一成員，并且它是未被標(biāo)記的。2while（C中存在尚未被標(biāo)記的子集T）do { 標(biāo)記T； for每個(gè)輸入字母ado { U:=-closure(move(T,a))； ifU不在C中then 將U作為未標(biāo)記的子集加在C中 } }6/3/2023172.4.3DFAM的化簡(jiǎn)

(DFAMinimization)NFA確定化所得的DFA可能含有多余的狀態(tài),需化簡(jiǎn)。所謂DFAM的化簡(jiǎn)，是指尋找一個(gè)狀態(tài)數(shù)比M少的DFAM'，使得L(M)=L(M')。

化簡(jiǎn)后的DFAM'滿足下述條件：

(1)無多余狀態(tài)

(死狀態(tài))；

(2)狀態(tài)集中無相互等價(jià)（不可區(qū)別）的狀態(tài)。

6/3/202318

兩個(gè)狀態(tài)相互等價(jià)是指:對(duì)于給定的DFAM,假定狀態(tài)s1,s2∈S且s1≠s2,若從s1出發(fā)能識(shí)別字符串而停于終態(tài),從s2出發(fā)也能識(shí)別而停于終態(tài);反之,若從s2出發(fā)能識(shí)別而停于終態(tài),從s1出發(fā)也能識(shí)別而停于終態(tài),則稱s1和s2等價(jià),否則稱s1和s2是可區(qū)分的。

假定狀態(tài)s1,s2∈S且s1≠s2,若s1和s2通過同一字符(串)到達(dá)了可區(qū)分的狀態(tài)，則s1和s2也是可區(qū)分的。6/3/202319DFAM的狀態(tài)最小化過程：將M的狀態(tài)集分割成一些不相交的子集，使得任意兩個(gè)不同子集的狀態(tài)是可區(qū)分的，而同一子集中的任意兩個(gè)狀態(tài)都是等價(jià)的。

最后,從每個(gè)子集中選出一種狀態(tài)，同時(shí)消去其它等價(jià)狀態(tài)，就得到最簡(jiǎn)的DFAM'且L(M)=L(M')。

6/3/202320DFAM的化簡(jiǎn)方法

(Hopcroft算法)

：(1)首先將DFAM的狀態(tài)集S中的終態(tài)與非終態(tài)分開,形成兩個(gè)子集,得到基本劃分。(2)對(duì)當(dāng)前已劃分出的I(1),I(2),…,I(m)子集,看每個(gè)I是否能進(jìn)一步劃分。對(duì)某個(gè)I(i)={s1,s2,…,sk},若存在輸入字符a∈Σ使得Ia(i)不全包含在當(dāng)前劃分的某個(gè)子集I(j)中,即跨越兩個(gè)子集,則將I(i)一分為二(下頁(yè))。(3)重復(fù)(2),直到每個(gè)子集均不能再分。

不能再分是指子集要么僅有一個(gè)狀態(tài)，要么有多個(gè)狀態(tài)但這些狀態(tài)不可區(qū)分。6/3/202321(a)無需劃分(b)需劃分s4s3s3s1s2s1s2aaaas46/3/202322如何進(jìn)行子集的劃分呢？假定當(dāng)前子集I(i)={s1,s2,…},其中s1和s2經(jīng)過有向邊a分別到達(dá)狀態(tài)t1和t2,而t1和t2分屬于當(dāng)前已劃出的兩個(gè)不同子集I(j)和I(k),則應(yīng)將I(i)分為兩部分：

I(i1)={s|s∈I(i)且s經(jīng)有向邊a到達(dá)t1}I(i2)=I(i)?I(i1)(由于t1和t2是可區(qū)分的，因此I(i1)中的狀態(tài)與I(i2)中的狀態(tài)可區(qū)分)6/3/202323劃分結(jié)束后,子集個(gè)數(shù)不再增加,從每個(gè)子集中選一個(gè)狀態(tài)形成新的DFA。例如，I(i)={s1,s2,s3}

若挑選s1作為I(i)的代表，則原來指向s2和s3的有向邊均改為指向新DFA中的s1。若I(i)中含原來的初態(tài)，則s1為新初態(tài)；

若I(i)中含原來的終態(tài)，則s1為新終態(tài)。6/3/202324例2.9

化簡(jiǎn)由例2.8得到的DFA。23252426120abbaababbaabbab解:(1)先將狀態(tài)集S={0,1,2,3,4,5,6}劃分為終態(tài)集{3,4,5,6}和非終態(tài)集{0,1,2}。

(2)考察{0,1,2}a:因{0,2,1}a={1,3}不屬于

{3,4,5,6}和{0,1,2},故將{0,1,2}劃分為

{0,2}和{1}。6/3/202325(3)考察{0,2}b:因{0,2}b={2,4},不屬于已劃分出的某個(gè)子集,故{0,2}劃分為{0}和{2}。(4)考察{3,4,5,6}a：

{3,4,5,6}a={3,6},屬于{3,4,5,6},故不劃分。(5)考察{3,4,5,6}b：

{3,4,5,6}b={4,5},屬于{3,4,5,6},故不劃分。(6)按順序把狀態(tài)子集{0},{1},{2},{3,4,5,6}

重命名為0,1,2,3,得到化簡(jiǎn)后的DFAM'':6/3/202326Sab01213221333312033aabbbaab6/3/202327結(jié)論接受L的最小狀態(tài)有窮自動(dòng)機(jī)，若不計(jì)同構(gòu)則是唯一的。另一種等價(jià)的構(gòu)造方法：填表算法，參考本節(jié)最后的附加ppt。6/3/2023282.4.4正規(guī)式到有限自動(dòng)機(jī)構(gòu)造示例例2.10

試用DFA的等價(jià)性證明正規(guī)式

(a|b)*與(a*b*)*等價(jià)。解:(1)正規(guī)式(a|b)*對(duì)應(yīng)的NFA如下：X12Yaeeb6/3/202329用子集法確定化得如下轉(zhuǎn)換表:IIaIb{X,1,Y}{1,Y}{1,Y}{1,Y}{1,Y}{1,Y}Sab011111重命名轉(zhuǎn)換表得:6/3/202330于是得到DFA如下:0ab1ab0ba化簡(jiǎn):因{0,1}a={1},故不劃分。因{0,1}b={1},故不劃分。因此,最簡(jiǎn)DFA如下:6/3/202331IIaIb{X,1,2,3,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}{2,3,1,Y}Sab011111重命名得狀態(tài)轉(zhuǎn)換矩陣:由于(a|b)*和(a*b*)*對(duì)應(yīng)的狀態(tài)轉(zhuǎn)換矩陣相同,故二者等價(jià)。

(2)(a*b*)*對(duì)應(yīng)的NFA如圖2-20所示,

用子集法將NFA確定化得下述轉(zhuǎn)換表:6/3/202332例2.11C語(yǔ)言可接受的合法文件名為

device:name.extension

其中device:和.extension可省。假定device,name和extension都是字母串,長(zhǎng)度不限但至少為1,試畫出識(shí)別文件名的DFAM。

解:所求正規(guī)式為(cc*:|)cc*(.cc*|)

相應(yīng)的NFAM如下圖所示：X2Y1234c

:c·ccccεε6/3/202333首先進(jìn)行預(yù)處理。然后用子集法確定化、重命名。Sc:.01-112324--35--44-355---IIcI:I.{X,2}{1,3,Y}--{1,3,Y}{1,3,Y}{2}{4}{2}{3,Y}--{4}{Y}--{3,Y}{3,Y}--{Y}{Y}--6/3/202334240221325cc：cccc··于是得到DFA如下：最后對(duì)DFA化簡(jiǎn),化簡(jiǎn)后仍為上圖。6/3/202335例2.12

某高級(jí)程序語(yǔ)言無符號(hào)數(shù)的正規(guī)式為digit+(.digit+)?(e(+|?)?digit+)?

其中digit表示數(shù)字,()?表示()中內(nèi)容可有可無,試給出其DFAM。

解:用d代表digit，其NFA如下圖所示：X2Y1234dε5edd·dεde－dεd+6/3/202336II±IdI.Ie{X}—{1,Y}——{1,Y}—{1,Y}{2}{4,5}{2}—{3,Y}——{4,5}{5}{Y}——{3,Y}—{3,Y}—{4,5}{5}—{Y}——{Y}—{Y}——S±d.e0—1

1—1232—4——356——4—4—35—6——6—6————用子集法將NFAM確定化,然后重命名。6/3/2023370321522426ddedddedd－＋·于是得到下圖所示的DFAM':由狀態(tài)轉(zhuǎn)換矩陣可見,狀態(tài)5和6面對(duì)輸入符號(hào)的下一狀態(tài)相同,但狀態(tài)5為非終態(tài),狀態(tài)6為終態(tài),故上述DFA已為最簡(jiǎn)。6/3/202338例2.13

構(gòu)造一DFA,它接收Σ={a,b}上所有滿足下述條件的字符串:該字符串中的每個(gè)a都有至少一個(gè)b直接跟在其右邊。解:Σ={a,b},所求正規(guī)式為b*(abb*)*。

相應(yīng)的NFAM如下圖所示:X2Y12eeebabb*X2Y1eeeb342aebb6/3/202339IIaIb｛X,1,2,Y}｛3｝｛1,2,Y｝｛3｝—｛4,2,Y｝｛1,2,Y｝｛3｝｛1,2,Y｝｛4,2,Y｝｛3｝｛4,2,Y｝Sab0121—3212313用子集法將NFAM確定化,然后重命名。6/3/2023402023221abaabbb于是得到DFAM'

如下:6/3/20234120bb1a用DFAM的化簡(jiǎn)方法得到最終劃分：

{0,2,3},{1}重命名后得到化簡(jiǎn)的DFAM''如下:6/3/2023422.4.5從NFAM到正規(guī)表達(dá)式的轉(zhuǎn)換正規(guī)表達(dá)式和NFA等價(jià)任何一個(gè)正規(guī)表達(dá)式表示的語(yǔ)言，存在一個(gè)NFA識(shí)別（Thompson構(gòu)造法）任何一個(gè)NFA識(shí)別的語(yǔ)言，可以表示為一個(gè)正規(guī)表達(dá)式拓廣狀態(tài)轉(zhuǎn)換圖的概念，轉(zhuǎn)移符號(hào)可以用一個(gè)正規(guī)表達(dá)式標(biāo)記6/3/202343方法：

1.在M的狀態(tài)轉(zhuǎn)換圖上增加狀態(tài)X,Y，從X到初始狀態(tài)q0用弧連接，從M的所有終態(tài)到Y(jié)用弧連接，得到的新的NFA為M，它只有一個(gè)初始狀態(tài)X和一個(gè)終止?fàn)顟B(tài)Y。2.反復(fù)應(yīng)用以下三條規(guī)則，消去-NFAM中的狀態(tài)結(jié)點(diǎn)和弧，直至只剩下狀態(tài)結(jié)點(diǎn)X、Y及連接二者的弧。在消去的過程中，用正規(guī)表達(dá)式標(biāo)記弧。6/3/202344從FAM到正規(guī)式的轉(zhuǎn)換規(guī)則如下:sisjr1|r21.2.3.sjsir1r2*sjsir1r1r2sisjsir1r2sjskeesir1sjsk6/3/2023453.連接X、Y結(jié)點(diǎn)邊的標(biāo)記r

即為所求的正規(guī)表達(dá)式：XYrstart6/3/202346每次減少一個(gè)中間狀態(tài)iqdaeqcbjqdae*iqdce*bae*jqbce*6/3/202347最后的正規(guī)表達(dá)式r1*r2(r4|r3r1*r2)*fq2r3r1r0q4r6/3/20234815432rsvwtu(1)15432rsvwt|u(2)1254r(t|u)*vs(t|u)*ws(t|u)*vr(t|u)*w(3)消除狀態(tài)36/3/202349例1：給出下圖對(duì)應(yīng)的正規(guī)表達(dá)式。q0q2q11221206/3/202350第1步，增加狀態(tài)q和f，構(gòu)造-NFA：q0q2q1122120qf6/3/202351消除狀態(tài)q1得到：q0q220qf2|11*211*6/3/202352消除狀態(tài)q2得到：q00qf((11*)|((2|11*2)2*)6/3/202353消除狀態(tài)q0得到：qf|0*|0*((11*)|((2|11*2)2*)化簡(jiǎn)得：0*1*2*6/3/202354例2：給出偶數(shù)個(gè)0和偶數(shù)個(gè)1的字符串的正規(guī)表達(dá)式312011110000start偶0偶1奇0奇1奇0偶1偶0奇16/3/202355消除狀態(tài)1：3201110110100start006/3/202356消除狀態(tài)2：3011|0010|0101|10start00|116/3/202357消除狀態(tài)3：011|00(10|01)(00|11)*(01|10)startqf((00|11)|((10|01)(00|11)*(01|10)))*即：start6/3/202358作業(yè)：P31

2.4，2.7(畫出對(duì)應(yīng)的NFA即可)，2.8，2.106/3/202359另一種等價(jià)的構(gòu)造方法：填表算法狀態(tài)的等價(jià)性p和q等價(jià)：若兩個(gè)狀態(tài)不等價(jià)，則稱二者是可區(qū)分的。pqwworpqww6/3/202360DFAMinimization:ExamplefbcdeaghgfedcbInitializetableentries:Unmarked,emptylistAEBFCGDH00000000111111116/3/202361DFAMinimization:ExamplefbcdeaghgfedcbMarkpairsoffinal&

nonfinalstatesAEBFCGDH00000000111111116/3/202362fbcdeaghgfedcbDFAMinimization:ExampleForeachunmarkedpair&symbol,…d(b,0)?d(a,0)d(b,1)?d(a,1)AEBFCGDH0000000011111111g?bc?fMaybe.No!6/3/202363fbcdeaghgfedcbForeachunmarkedpair&symbol,…d