形式語言-第4章-正則表達(dá)式-課件

1、2022/10/121第4章 正則表達(dá)式 正則文法擅長語言的產(chǎn)生，有窮狀態(tài)自動(dòng)機(jī)擅長語言的識(shí)別。本章討論正則語言的正則表達(dá)式描述。它在對(duì)正則語言的表達(dá)上具有特殊的優(yōu)勢(shì)，為正則語言的計(jì)算機(jī)處理提供了方便條件。簡潔、更接近語言的集合表示和語言的計(jì)算機(jī)表示等。2022/10/101第4章 正則表達(dá)式 正則文法擅長語2022/10/122第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à)性證明。 2022/10/102第4章 正則表達(dá)式主要內(nèi)容2022/10/1234. 啟示 產(chǎn)生語言anbmck

2、|n，m，k1aicnbxam|i0,n1,m2,x為d和e組成的串 的正則文法為AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a2022/10/1034. 啟示 產(chǎn)生語言anbmck|2022/10/1244. 啟示 接受此語言的NFA M 2022/10/1044. 啟示 接受此語言的NFA M 2022/10/1254. 啟示 計(jì)算集合 set(q)set(A)=an|n0=a* set(B)= set(A)abn|n0 =anabm|m，n0 =a*ab*=a+b*set(C)= set(B)bc* =a*ab*bc*=a+b+c*set(D)= se

3、t(C) c=a+b+c*c =a+b+c+2022/10/1054. 啟示 計(jì)算集合 set(q)2022/10/1264. 啟示 set(E)= set(A)cc* =a*cc*=a*c+set(F)= set(E)bd，e*=a*c+bd，e*set(H)= set(F)aa*=a*c+bd，e*aa* =a*c+b d，e*a+set(I)= set(H)a=a*c+b d，e*a+aL(M)= set(D)set(H) = a+b+c+a*c+bd，e*a+a2022/10/1064. 啟示 set(E)= set(2022/10/1274. 啟示 根據(jù)集合運(yùn)算的定義，d，e=de。

4、從而，d，e*=(de)*。這樣可以將L(M)寫成如下形式：L(M)= a+b+c+a*c+b (de)*a+a 記作：a+b+c+a*c+b(d+e)*a+a= aa*bb*cc*+a*cc*b(d+e)* aaa* 2022/10/1074. 啟示 根據(jù)集合運(yùn)算的定義，2022/10/1284.2 RE的形式定義 正則表達(dá)式(regular expression，RE) 是上的RE，它表示語言； 是上的RE，它表示語言； 對(duì)于a，a是上的RE，它表示語言a；2022/10/1084.2 RE的形式定義 正則表達(dá)式(r2022/10/1294.2 RE的形式定義 如果r和s分別是上表示語言R

5、和S的RE，則： r與s的“和” (r+s)是上的RE，(r+s)表達(dá)的語言為RS； r與s的“乘積” (rs)是上的RE，(rs)表達(dá)的語言為RS； r的克林閉包(r*)是上的RE，(r*)表達(dá)的語言為R*。 只有滿足、的才是上的RE。2022/10/1094.2 RE的形式定義 如果r和s2022/10/12104.2 RE的形式定義 例 4-1 設(shè)=0，1 0，表示語言0； 1，表示語言1； (0+1)，表示語言0，1； (01)，表示語言01； (0+1)*)，表示語言0，1*； (00)(00)*)，表示語言0000*；2022/10/10104.2 RE的形式定義 例 4-1 20

6、22/10/12114.2 RE的形式定義 (0+1)*)(0+1)(0+1)*),表示語言0，1+； (0+1)*)000)(0+1)*)，表示0，1上的至少含有3個(gè)連續(xù)0的串組成的語言； (0+1)*)0)1)，表示所有以01結(jié)尾的0、1字符串組成的語言； (1(0+1)*)0)，表示所有以1開頭，并且以0結(jié)尾的0、1字符串組成的語言。 2022/10/10114.2 RE的形式定義 (2022/10/12124.2 RE的形式定義 約定 r的正閉包r+表示r與(r*)的乘積以及(r*)與r的乘積： r+=(r(r*)=(r*)r) 閉包運(yùn)算的優(yōu)先級(jí)最高，乘運(yùn)算的優(yōu)先級(jí)次之，加運(yùn)算“+”的

7、優(yōu)先級(jí)最低。所以，在意義明確時(shí)，可以省略其中某些括號(hào)。 (0+1)*)000)(0+1)*)=(0+1)*000(0+1)* 2022/10/10124.2 RE的形式定義 約定 2022/10/12134.2 RE的形式定義 (0+1)*)(0+1)(0+1)*)=(0+1)*(0+1)(0+1)* 在意義明確時(shí)，RE r表示的語言記為L(r)，也可以直接地記為r。 加、乘、閉包運(yùn)算均執(zhí)行左結(jié)合規(guī)則。2022/10/10134.2 RE的形式定義 (0+2022/10/12144.2 RE的形式定義相等(equivalence)r、s是字母表上的一個(gè)RE，如果L(r)=L(s)，則稱r與s相

8、等，記作r=s 。相等也稱為等價(jià)。幾個(gè)基本結(jié)論 結(jié)合律：(rs)t=r(st) (r+s)+t=r+(s+t) 分配律：r(s+t)=rs+rt (s+t)r=sr+tr2022/10/10144.2 RE的形式定義相等(equi2022/10/12154.2 RE的形式定義 交換律：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。 2022/10/10154.2 RE的形式定義 交換律：2022/10/12164.2 RE的形式定義 L(rs)=L(r)L(s)。 L(r+s)

9、=L(r)L(s)。 L(r*)=(L(r)* 。 L(*)=。 L(r+)*)=L(r*)。 L(r*)*)=L(r*)。 L(r*s*)*)=L(r+s)*)。 如果L(r) L(s)，則r+s=s。2022/10/10164.2 RE的形式定義 L(rs)2022/10/12174.2 RE的形式定義 L(rn)=(L(r)n 。 rnrm=rn+m 。一般地， r+r，(rs)n rnsn，rssr。冪 r是字母表上的RE，r的n次冪定義為 r0=。 rn=rn-1r。 2022/10/10174.2 RE的形式定義 L(rn)2022/10/12184.2 RE的形式定義例 4-2

10、設(shè)=0，100表示語言00；(0+1)*00(0+1)*表示所有的至少含兩個(gè)連續(xù)0的0、1串組成的語言；(0+1)*1(0+1)9表示所有的倒數(shù)第10個(gè)字符為1的串組成的語言；2022/10/10184.2 RE的形式定義例 4-2 設(shè)2022/10/12194.2 RE的形式定義L(0+1)*011)=x|x是以011結(jié)尾的0、1串；L(0+1+2+)=0n1m2k|m，n，k1；L(0*1*2*)=0n1m2k|m，n，k0；L(1(0+1)*1+0(0+1)*0)=x|x的開頭字符與尾字符相同。2022/10/10194.2 RE的形式定義L(0+1)2022/10/12204.3 RE

11、與FA等價(jià) 正則表達(dá)式r稱為與FA M等價(jià)，如果L(r)=L(M)。從開始狀態(tài)出發(fā)，根據(jù)狀態(tài)之間按照轉(zhuǎn)移所確定的后繼關(guān)系，依次計(jì)算出所給FA的各個(gè)狀態(tài)q對(duì)應(yīng)的set(q)，并且最終得到相應(yīng)的FA接受的語言的RE表示。 尋找一種比較“機(jī)械”的方法，使得計(jì)算機(jī)系統(tǒng)能夠自動(dòng)完成FA與RE之間的轉(zhuǎn)換。 2022/10/10204.3 RE與FA等價(jià) 正則表達(dá)式r2022/10/12214.3.1 RE到FA的等價(jià)變換 0對(duì)應(yīng)的FA01對(duì)應(yīng)的FA2022/10/10214.3.1 RE到FA的等價(jià)變換 02022/10/12224.3.1 RE到FA的等價(jià)變換 0+1對(duì)應(yīng)的FA2022/10/10224

12、.3.1 RE到FA的等價(jià)變換 02022/10/12234.3.1 RE到FA的等價(jià)變換 0*對(duì)應(yīng)的FA2022/10/10234.3.1 RE到FA的等價(jià)變換 02022/10/12244.3.1 RE到FA的等價(jià)變換 定理 4-1 RE表示的語言是RL。證明：施歸納于正則表達(dá)式中所含的運(yùn)算符的個(gè)數(shù)n，證明對(duì)于字母表上的任意正則表達(dá)式r，存在FA M，使得L(M) = L(r) 。M恰有一個(gè)終止?fàn)顟B(tài)。M在終止?fàn)顟B(tài)下不作任何移動(dòng)。 2022/10/10244.3.1 RE到FA的等價(jià)變換 定2022/10/12254.3.1 RE到FA的等價(jià)變換 n=0 r=r= r=a 2022/10/1

13、0254.3.1 RE到FA的等價(jià)變換 n2022/10/12264.3.1 RE到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) 。Q1Q2=。 n=k2022/10/10264.3.1 RE到FA的等價(jià)變換 設(shè)2022/10/1227n=k+1 r=r1+r2取q0，fQ1Q2，令M=(Q1Q2q0，f，q0，f) (q0，)=q01，q02； 對(duì)qQ1，a，(q，a)=1(q，a); 對(duì)qQ2，a，(q，a)=2(q，a)； (f1，)=f； (f2，)=f。 2022

14、/10/1027n=k+1 r=r1+r2取q0，f2022/10/12284.3.1 RE到FA的等價(jià)變換 n=k+1 r=r1+r2 2022/10/10284.3.1 RE到FA的等價(jià)變換 n2022/10/12294.3.1 RE到FA的等價(jià)變換 M=(Q1Q2，q01，f2) 對(duì)qQ1-f1，a(q，a)=1(q，a)；對(duì)qQ2-f2，a(q，a)=2(q，a)； (f1，)=q022022/10/10294.3.1 RE到FA的等價(jià)變換 M2022/10/12304.3.1 RE到FA的等價(jià)變換 r=r1r2 2022/10/10304.3.1 RE到FA的等價(jià)變換 r2022/1

15、0/12314.3.1 RE到FA的等價(jià)變換 M=(Q1q0，f，q0，f)其中q0，fQ1，定義為 對(duì)qQ1-f1，a，(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。2022/10/10314.3.1 RE到FA的等價(jià)變換 M2022/10/12324.3.1 RE到FA的等價(jià)變換 r=r1* 2022/10/10324.3.1 RE到FA的等價(jià)變換 r2022/10/12334.3.1 RE到FA的等價(jià)變換 按照定理4-1證明給出的方法構(gòu)造一個(gè)給定RE的等價(jià)FA時(shí)，該FA有可能含有許多的空移動(dòng)?？梢园凑兆约簩?duì)給定RE的“理解”以及對(duì)FA的 “理解” “直接地

16、”構(gòu)造出一個(gè)比較“簡單”的FA。定理證明中所給的方法是機(jī)械的。由于“直接地”構(gòu)造出的FA的正確性依賴于構(gòu)造者的“理解”，所以它的正確性缺乏有力的保證。 2022/10/10334.3.1 RE到FA的等價(jià)變換 按2022/10/12344.3.1 RE到FA的等價(jià)變換 例 4-3 構(gòu)造與 (0+1)*0+(00)*等價(jià)的FA。 2022/10/10344.3.1 RE到FA的等價(jià)變換 例2022/10/12354.3.1 RE到FA的等價(jià)變換按照對(duì)(0+1)*0+(00)*的“理解” “直接地”構(gòu)造出的FA。2022/10/10354.3.1 RE到FA的等價(jià)變換按照2022/10/12364

17、.3.2 RL可以用RE表示 計(jì)算DFA的每個(gè)狀態(tài)對(duì)應(yīng)的集合字母表的克林閉包的等價(jià)分類，是具有啟發(fā)意義的。 這個(gè)計(jì)算過程難以“機(jī)械”地進(jìn)行。 計(jì)算q1到q2的一類串的集合：Rkij 。圖上作業(yè)法。2022/10/10364.3.2 RL可以用RE表示 計(jì)算2022/10/12374.3.2 RL可以用RE表示定理4-2 RL可以用RE表示。設(shè)DFA M=(q1，q2，qn，q1，F(xiàn))Rkij=x|(qi，x)=qj而且對(duì)于x的任意前綴y(yx，y)，如果(qi，y)=ql，則lk。 2022/10/10374.3.2 RL可以用RE表示定理42022/10/12384.3.2 RL可以用RE表

18、示R0ij= a|(qi，a)=qj如果ij a|(qi，a)=qj如果i=j Rkij= Rk-1ik( Rk-1kk)* Rk-1kj Rk-1ij 2022/10/10384.3.2 RL可以用RE表示R0i2022/10/12394.3.2 RL可以用RE表示圖上作業(yè)法 啟示2022/10/10394.3.2 RL可以用RE表示圖上作2022/10/12404.3.2 RL可以用RE表示圖上作業(yè)法操作步驟 預(yù)處理： 用標(biāo)記為X和Y的狀態(tài)將M“括起來”： 在狀態(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(qF)的狀態(tài)到標(biāo)記為Y的狀態(tài)分別

19、引一條標(biāo)記為的弧。 去掉所有的不可達(dá)狀態(tài)。2022/10/10404.3.2 RL可以用RE表示圖上作2022/10/12414.3.2 RL可以用RE表示 對(duì)通過步驟(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è)并行弧。 2022/10/10414.3.2 RL可以用RE表示 對(duì)2022/10/12424.3.2 RL可以用RE表示去狀態(tài)1如果從q到p有一條標(biāo)記為r1的弧，從p到t有一條標(biāo)記為r2的弧，不存在從狀態(tài)p到

20、狀態(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的弧代替。 2022/10/10424.3.2 RL可以用RE表示去狀態(tài)2022/10/12434.3.2 RL可以用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)的弧全部刪除。 2022/10/10434.3.2 RL可以用RE表示去

21、狀態(tài)2022/10/12444.3.2 RL可以用RE表示 從標(biāo)記為X的狀態(tài)到標(biāo)記為Y的狀態(tài)的弧的標(biāo)記為所求的正則表達(dá)式。如果此弧不存在，則所求的正則表達(dá)式為。 2022/10/10444.3.2 RL可以用RE表示 從2022/10/12454.3.2 RL可以用RE表示例 4-4 求圖4-14所示的DFA等價(jià)的RE 。2022/10/10454.3.2 RL可以用RE表示例 42022/10/12464.3.2 RL可以用RE表示預(yù)處理。2022/10/10464.3.2 RL可以用RE表示預(yù)處理2022/10/12474.3.2 RL可以用RE表示去掉狀態(tài)q3。2022/10/10474

22、.3.2 RL可以用RE表示去掉狀2022/10/12484.3.2 RL可以用RE表示去掉狀態(tài)q4。2022/10/10484.3.2 RL可以用RE表示去掉狀2022/10/12494.3.2 RL可以用RE表示合并從標(biāo)記為q2的狀態(tài)到標(biāo)記為Y的狀態(tài)的兩條并行弧。 2022/10/10494.3.2 RL可以用RE表示合并從2022/10/12504.3.2 RL可以用RE表示去掉狀態(tài)q0。2022/10/10504.3.2 RL可以用RE表示去掉狀2022/10/12514.3.2 RL可以用RE表示并弧。 2022/10/10514.3.2 RL可以用RE表示并弧。2022/10/12

23、524.3.2 RL可以用RE表示去掉狀態(tài)q1。2022/10/10524.3.2 RL可以用RE表示去掉狀2022/10/12534.3.2 RL可以用RE表示去掉狀態(tài)q2。1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)(00*+00*1)就是所求。 2022/10/10534.3.2 RL可以用RE表示去掉狀2022/10/12544.3.2 RL可以用RE表示幾點(diǎn)值得注意的問題 如果去狀態(tài)的順序不一樣，則得到的RE可能在形式是不一樣，但它們都是等價(jià)的。 當(dāng)DFA的終止?fàn)顟B(tài)都是不可達(dá)的時(shí)候，狀態(tài)轉(zhuǎn)移圖中必不存在從開始狀態(tài)到終止?fàn)顟B(tài)的路。此時(shí)，相應(yīng)的RE為

24、。 不計(jì)算自身到自身的弧，如果狀態(tài)q的入度為n，出度為m，則將狀態(tài)q及其相關(guān)的弧去掉之后，需要添加n*m條新弧。 2022/10/10544.3.2 RL可以用RE表示幾點(diǎn)值2022/10/12554.3.2 RL可以用RE表示 對(duì)操作的步數(shù)施歸納，可以證明它的正確性。推論4-1 正則表達(dá)式與FA、正則文法等價(jià)，是正則語言的表示模型。2022/10/10554.3.2 RL可以用RE表示 對(duì)2022/10/12564.4 正則語言等價(jià)模型的總結(jié) AaB B(A,a)Aa qf(A,a)(q,a)=p qap(q,a)=pF qaRGGDFANFARE-NFADFA(P,a)=NFA(P,a)NFA(q，a)=(q，a)圖上作業(yè)法歸納2022/10/10564.4 正則語言等價(jià)模型的總結(jié) A2022/10/