第四章正則表達(dá)式第1頁(yè)，共58頁(yè)，2023年，2月20日，星期三第4章正則表達(dá)式主要內(nèi)容典型RE的構(gòu)造。與RE等價(jià)FA的構(gòu)造方法。與DFA等價(jià)的RE的構(gòu)造。重點(diǎn)RE的概念。RE與DFA的等價(jià)性。難點(diǎn)：RE與DFA的等價(jià)性證明。

第2頁(yè)，共58頁(yè)，2023年，2月20日，星期三在前面我們已經(jīng)用到了一些類(lèi)似正則表達(dá)式來(lái)表示語(yǔ)言(紅色部分)：–L(G)={0n|n≥1}–L(G)={anbn|n≥1}–L(G)={0n1m2k|n,m,k≥1}這種表示法的優(yōu)點(diǎn)：–

比文法和有窮狀態(tài)自動(dòng)機(jī)簡(jiǎn)單；–

更接近集合表示和計(jì)算機(jī)表示。第3頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.1啟示產(chǎn)生語(yǔ)言{anbmck|n,m,k≥1}∪{aicnbxam|i≥0,n≥1,m≥2,x為d和e組成的串}的正則文法為AaA|aB|cEBbB|bCCcC|cEcE|bFFdF|eF|aHHaH|a第4頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.1啟示接受此語(yǔ)言的NFAM

第5頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.1啟示計(jì)算集合

set(q)set(A)={an|n≥0}={a}*

set(B)=set(A){a}{bn|n≥0} ={anabm|m,n≥0} ={a}*{a}*={a}+*set(C)=set(B){c}* ={a}*{a}*{c}*={a}++{c}*set(D)=set(C){c}={a}++{c}*{c} ={a}++{c}+第6頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.1啟示set(E)=set(A){c}{c}*

={a}*{c}{c}*={a}*{c}+set(F)=set(E){d,e}*={a}*{c}+{d,e}*set(H)=set(F){a}{a}*={a}*{c}+

{d,e}*{a}{a}*

={a}*{c}+{d,e}*{a}+set(I)=set(H){a}={a}*{c}+

{d,e}*{a}+{a}L(M)=set(D)∪set(H) ={a}++{c}+∪{a}*{c}+

{d,e}*{a}+{a}第7頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.1啟示根據(jù)集合運(yùn)算的定義,{d,e}=ndrfltp∪{e}。從而, {d,e}*=(jpbflhv∪{e})*。這樣可以將L(M)寫(xiě)成如下形式：

L(M)={a}++{c}+∪{a}*{c}+

(rfhllxt∪{e})*{a}+{a}記作：

a+b+c++a*c+(d+e)*a+a=aa*bb*cc*+a*cc*b(d+e)*aaa*

第8頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義正則表達(dá)式(regularexpression,RE)⑴Φ是∑上的RE,它表示語(yǔ)言Φ；⑵ε是∑上的RE,它表示語(yǔ)言{ε}；⑶對(duì)于a∈∑,a是∑上的RE,它表示語(yǔ)言{a}；⑷如果r和s分別是∑上表示語(yǔ)言R和S的RE,則：

r與s的“和”(r+s)是∑上的RE,(r+s)表達(dá)的語(yǔ)言為R∪S；

r與s的“乘積”(rs)是∑上的RE,(rs)表達(dá)的語(yǔ)言為RS；

r的克林閉包(r*)是∑上的RE,(r*)表達(dá)的語(yǔ)言為R*。⑸只有滿(mǎn)足⑴、⑵、⑶、⑷的才是∑上的RE。第9頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義

例4-1

設(shè)∑={0,1}⑴0,表示語(yǔ)言{0}；⑵1,表示語(yǔ)言{1}；⑶(0+1),表示語(yǔ)言{0,1}；⑷(01),表示語(yǔ)言{01}；⑸((0+1)*),表示語(yǔ)言{0,1}*；⑹((00)((00)*)),表示語(yǔ)言{00}{00}*；第10頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義

⑺((((0+1)*)(0+1))((0+1)*)),表示語(yǔ)言{0,1}+；⑻((((0+1)*)000)((0+1)*)),表示{0,1}上的至少含有3個(gè)連續(xù)0的串組成的語(yǔ)言；⑼((((0+1)*)0)1),表示所有以01結(jié)尾的0、1字符串組成的語(yǔ)言；⑽(1(((0+1)*)0)),表示所有以1開(kāi)頭,并且以0結(jié)尾的0、1字符串組成的語(yǔ)言。

第11頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義

約定⑴r的正閉包r+表示r與(r*)的乘積以及(r*)與r的乘積：

r+=(r(r*))=((r*)r)⑵閉包運(yùn)算的優(yōu)先級(jí)最高,乘運(yùn)算的優(yōu)先級(jí)次之,加運(yùn)算“+”的優(yōu)先級(jí)最低。所以,在意義明確時(shí),可以省略其中某些括號(hào)。((((0+1)*)000)((0+1)*))=(0+1)*000(0+1)*

第12頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義

((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*

⑶在意義明確時(shí),REr表示的語(yǔ)言記為L(zhǎng)(r),也可以直接地記為r。⑷加、乘、閉包運(yùn)算均執(zhí)行左結(jié)合規(guī)則。第13頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義相等(equivalence)r、s是字母表∑上的一個(gè)RE,如果L(r)=L(s),則稱(chēng)r與s相等,記作r=s。相等也稱(chēng)為等價(jià)?；窘Y(jié)論⑴結(jié)合律：(rs)t=r(st) (r+s)+t=r+(s+t)⑵分配律：r(s+t)=rs+rt (s+t)r=sr+tr第14頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義⑶交換律： r+s=s+r。⑷冪等律： r+r=r。⑸加法運(yùn)算零元素：r+Φ=r。⑹乘法運(yùn)算單位元：rε=εr=r。⑺乘法運(yùn)算零元素：rΦ=Φr=Φ。⑻L(Φ)=Φ。⑼L(ε)={ε}。⑽L(a)={a}。

第15頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義⑾L(rs)=L(r)L(s)。⑿L(r+s)=L(r)∪L(s)。⒀L(r*)=(L(r))*。⒁L(Φ*)={ε}。⒂L((r+ε)*)=L(r*)。⒃L(fǎng)((r*)*)=L(r*)。⒄L((r*s*)*)=L((r+s)*)。⒅如果L(r)L(s),則r+s=s。第16頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義⒆L(rn)=(L(r))n。⒇rnrm=rn+m。一般地,r+ε≠r,(rs)n≠rnsn,rs≠sr。冪r是字母表∑上的RE,r的n次冪定義為⑴r0=ε。⑵rn=rn-1r。

第17頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義例4-2

設(shè)∑={0,1}00表示語(yǔ)言{00}；(0+1)*00(0+1)*表示所有的至少含兩個(gè)連續(xù)0的0、1串組成的語(yǔ)言；(0+1)*1(0+1)9表示所有的倒數(shù)第10個(gè)字符為1的串組成的語(yǔ)言；第18頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.2RE的形式定義L((0+1)*011)={x|x是以011結(jié)尾的0、1串}；L(0+1+2+)={0n1m2k|m,n,k≥1}；L(0*1*2*)={0n1m2k|m,n,k≥0}；L(1(0+1)*1+0(0+1)*0))={x|x的開(kāi)頭字符與尾字符相同}。第19頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3RE與FA等價(jià)正則表達(dá)式r稱(chēng)為與FAM等價(jià),如果L(r)=L(M)。從開(kāi)始狀態(tài)出發(fā),根據(jù)狀態(tài)之間按照轉(zhuǎn)移所確定的后繼關(guān)系,依次計(jì)算出所給FA的各個(gè)狀態(tài)q對(duì)應(yīng)的set(q),并且最終得到相應(yīng)的FA接受的語(yǔ)言的RE表示。尋找一種比較“機(jī)械”的方法,使得計(jì)算機(jī)系統(tǒng)能夠自動(dòng)完成FA與RE之間的轉(zhuǎn)換。

第20頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換0對(duì)應(yīng)的FA01對(duì)應(yīng)的FA第21頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換0+1對(duì)應(yīng)的FA第22頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換0*對(duì)應(yīng)的FA第23頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換定理4-1

RE表示的語(yǔ)言是RL。證明：施歸納于正則表達(dá)式中所含的運(yùn)算符的個(gè)數(shù)n,證明對(duì)于字母表∑上的任意正則表達(dá)式r,存在FAM,使得L(M)=L(r)。M恰有一個(gè)終止?fàn)顟B(tài)。M在終止?fàn)顟B(tài)下不作任何移動(dòng)。第24頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換n=0

r=εr=Φ

r=a

第25頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換設(shè)結(jié)論對(duì)于n=k時(shí)成立,此時(shí)有如下FA：M1=(Q1,∑,δ1,q01,{f1})M2=(Q2,∑,δ2,q02,{f2})L(M1)=L(r1),L(M2)=L(r2)。Q1∩Q2=Φ。

n=k第26頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換n=k+1

r=r1+r2取q0,fQ1∪Q2,令

M=(Q1∪Q2∪{q0,f},∑,δ,q0,{f})①δ(q0,ε)={q01,q02}；②對(duì)q∈Q1,a∈∑∪{ε},δ(q,a)=δ1(q,a);

對(duì)q∈Q2,a∈∑∪{ε},δ(q,a)=δ2(q,a)；③δ(f1,ε)={f}；④δ(f2,ε)={f}。第27頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換n=k+1

r=r1+r2

第28頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換M=(Q1∪Q2,∑,δ,q01,{f2})

①

對(duì)q∈Q1-{f1},a∈∑∪{ε}δ(q,a)=δ1(q,a)；②

對(duì)q∈Q2-{f2},a∈∑∪{ε}δ(q,a)=δ2(q,a)；③δ(f1,ε)={q02}第29頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換r=r1r2

第30頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換M=(Q1∪{q0,f},∑,δ,q0,{f})其中q0,fQ1,定義δ為①

對(duì)q∈Q1-{f1},a∈∑, δ(q,a)=δ1(q,a)。②

δ(f1,ε)={q01,f}。③δ(q0,ε)={q01,f}。第31頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換r=r1*

第32頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換按照定理4-1證明給出的方法構(gòu)造一個(gè)給定RE的等價(jià)FA時(shí),該FA有可能含有許多的空移動(dòng)?？梢园凑兆约簩?duì)給定RE的“理解”以及對(duì)FA的“理解”“直接地”構(gòu)造出一個(gè)比較“簡(jiǎn)單”的FA。定理證明中所給的方法是機(jī)械的。由于“直接地”構(gòu)造出的FA的正確性依賴(lài)于構(gòu)造者的“理解”,所以它的正確性缺乏有力的保證。第33頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換例4-3

構(gòu)造與(0+1)*0+(00)*等價(jià)的FA。

第34頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.1RE到FA的等價(jià)變換按照對(duì)(0+1)*0+(00)*的“理解”“直接地”構(gòu)造出的FA。0S101第35頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示計(jì)算DFA的每個(gè)狀態(tài)對(duì)應(yīng)的集合——字母表的克林閉包的等價(jià)分類(lèi),是具有啟發(fā)意義的。這個(gè)計(jì)算過(guò)程難以“機(jī)械”地進(jìn)行。計(jì)算q1到q2的一類(lèi)串的集合：Rkij

。圖上作業(yè)法。第36頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示定理4-2

RL可以用RE表示。設(shè)DFAM=({q1,q2,…,qn},∑,δ,q1,F)Rkij={x|δ(qi,x)=qj而且對(duì)于x的任意前綴y(y≠x,y≠ε),如果δ(qi,y)=ql,則l≤k}。第37頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示R0ij=

{a|δ(qi,a)=qj} 如果i≠j

{a|δ(qi,a)=qj}∪{ε} 如果i=jRkij=Rk-1ik(Rk-1kk)*Rk-1kjRk-1ij

第38頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示圖上作業(yè)法啟示第39頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示圖上作業(yè)法操作步驟⑴預(yù)處理：①用標(biāo)記為X和Y的狀態(tài)將M“括起來(lái)”：在狀態(tài)轉(zhuǎn)移圖中增加標(biāo)記為X和Y的狀態(tài),從標(biāo)記為X的狀態(tài)到標(biāo)記為q0的狀態(tài)引一條標(biāo)記為ε的??；從標(biāo)記為q(q∈F)的狀態(tài)到標(biāo)記為Y的狀態(tài)分別引一條標(biāo)記為ε的弧。②去掉所有的不可達(dá)狀態(tài)。第40頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示⑵對(duì)通過(guò)步驟(1)處理所得到的狀態(tài)轉(zhuǎn)移圖重復(fù)如下操作,直到該圖中不再包含除了標(biāo)記為X和Y外的其他狀態(tài),并且這兩個(gè)狀態(tài)之間最多只有一條弧。并弧將從q到p的標(biāo)記為r1,r2,…,rg并行弧用從q到p的、標(biāo)記為r1+r2+…+rg的弧取代這g個(gè)并行弧。

第41頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去狀態(tài)1如果從q到p有一條標(biāo)記為r1的弧,從p到t有一條標(biāo)記為r2的弧,不存在從狀態(tài)p到狀態(tài)p的弧,將狀態(tài)p和與之關(guān)聯(lián)的這兩條弧去掉,用一條從q到t的標(biāo)記為r1r2的弧代替。去狀態(tài)2如果從q到p有一條標(biāo)記為r1的弧,從p到t有一條標(biāo)記為r2的弧,從狀態(tài)p到狀態(tài)p標(biāo)記為r3的弧,將狀態(tài)p和與之關(guān)聯(lián)的這三條弧去掉,用一條從q到t的標(biāo)記為r1r3*r2的弧代替。

第42頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去狀態(tài)3如果圖中只有三個(gè)狀態(tài),而且不存在從標(biāo)記為X的狀態(tài)到達(dá)標(biāo)記為Y的狀態(tài)的路,則將除標(biāo)記為X的狀態(tài)和標(biāo)記為Y的狀態(tài)之外的第3個(gè)狀態(tài)及其相關(guān)的弧全部刪除。

⑶從標(biāo)記為X的狀態(tài)到標(biāo)記為Y的狀態(tài)的弧的標(biāo)記為所求的正則表達(dá)式。如果此弧不存在,則所求的正則表達(dá)式為Φ。

第43頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示例4-4

求圖4-14所示的DFA等價(jià)的RE

。第44頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示預(yù)處理：第45頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去掉狀態(tài)q3：第46頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去掉狀態(tài)q4：第47頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示合并從標(biāo)記為q2的狀態(tài)到標(biāo)記為Y的狀態(tài)的兩條并行弧。

第48頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去掉狀態(tài)q0：11*0第49頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示并弧：

第50頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去掉狀態(tài)q1：第51頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示去掉狀態(tài)q2：1*0(11*0)*0((00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。

第52頁(yè)，共58頁(yè)，2023年，2月20日，星期三4.3.2RL可以用RE表示幾點(diǎn)值得注意的問(wèn)題⑴如果去狀態(tài)的順序不一樣,則得到的RE可能在形式是不一樣,但它們都是等價(jià)的。⑵當(dāng)DFA的終止?fàn)顟B(tài)都是不可達(dá)的時(shí)候,狀態(tài)轉(zhuǎn)移圖中必不存在從開(kāi)始狀態(tài)到終止?fàn)顟B(tài)的路。此時(shí),相應(yīng)的RE為Φ