1、2022/10/121第4章 正則表達式 正則文法擅長語言的產生，有窮狀態自動機擅長語言的識別。本章討論正則語言的正則表達式描述。它在對正則語言的表達上具有特殊的優勢，為正則語言的計算機處理提供了方便條件。簡潔、更接近語言的集合表示和語言的計算機表示等。2022/10/101第4章 正則表達式 正則文法擅長語2022/10/122第4章 正則表達式主要內容典型RE的構造。與RE等價FA的構造方法。與DFA等價的RE的構造。重點RE的概念。RE與DFA的等價性。難點：RE與DFA的等價性證明。 2022/10/102第4章 正則表達式主要內容2022/10/1234. 啟示 產生語言anbmck

2、|n，m，k1aicnbxam|i0,n1,m2,x為d和e組成的串 的正則文法為AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a2022/10/1034. 啟示 產生語言anbmck|2022/10/1244. 啟示 接受此語言的NFA M 2022/10/1044. 啟示 接受此語言的NFA M 2022/10/1254. 啟示 計算集合 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. 啟示 計算集合 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. 啟示 根據集合運算的定義，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. 啟示 根據集合運算的定義，2022/10/1284.2 RE的形式定義 正則表達式(regular expression，RE) 是上的RE，它表示語言； 是上的RE，它表示語言； 對于a，a是上的RE，它表示語言a；2022/10/1084.2 RE的形式定義 正則表達式(r2022/10/1294.2 RE的形式定義 如果r和s分別是上表示語言R

5、和S的RE，則： r與s的“和” (r+s)是上的RE，(r+s)表達的語言為RS； r與s的“乘積” (rs)是上的RE，(rs)表達的語言為RS； r的克林閉包(r*)是上的RE，(r*)表達的語言為R*。 只有滿足、的才是上的RE。2022/10/1094.2 RE的形式定義 如果r和s2022/10/12104.2 RE的形式定義 例 4-1 設=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個連續0的串組成的語言； (0+1)*)0)1)，表示所有以01結尾的0、1字符串組成的語言； (1(0+1)*)0)，表示所有以1開頭，并且以0結尾的0、1字符串組成的語言。 2022/10/10114.2 RE的形式定義 (2022/10/12124.2 RE的形式定義 約定 r的正閉包r+表示r與(r*)的乘積以及(r*)與r的乘積： r+=(r(r*)=(r*)r) 閉包運算的優先級最高，乘運算的優先級次之，加運算“+”的

7、優先級最低。所以，在意義明確時，可以省略其中某些括號。 (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)* 在意義明確時，RE r表示的語言記為L(r)，也可以直接地記為r。 加、乘、閉包運算均執行左結合規則。2022/10/10134.2 RE的形式定義 (0+2022/10/12144.2 RE的形式定義相等(equivalence)r、s是字母表上的一個RE，如果L(r)=L(s)，則稱r與s相

8、等，記作r=s 。相等也稱為等價。幾個基本結論 結合律：(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。 加法運算零元素：r+=r。 乘法運算單位元：r=r=r。 乘法運算零元素：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、設=0，100表示語言00；(0+1)*00(0+1)*表示所有的至少含兩個連續0的0、1串組成的語言；(0+1)*1(0+1)9表示所有的倒數第10個字符為1的串組成的語言；2022/10/10184.2 RE的形式定義例 4-2 設2022/10/12194.2 RE的形式定義L(0+1)*011)=x|x是以011結尾的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等價 正則表達式r稱為與FA M等價，如果L(r)=L(M)。從開始狀態出發，根據狀態之間按照轉移所確定的后繼關系，依次計算出所給FA的各個狀態q對應的set(q)，并且最終得到相應的FA接受的語言的RE表示。 尋找一種比較“機械”的方法，使得計算機系統能夠自動完成FA與RE之間的轉換。 2022/10/10204.3 RE與FA等價 正則表達式r2022/10/12214.3.1 RE到FA的等價變換 0對應的FA01對應的FA2022/10/10214.3.1 RE到FA的等價變換 02022/10/12224.3.1 RE到FA的等價變換 0+1對應的FA2022/10/10224

12、.3.1 RE到FA的等價變換 02022/10/12234.3.1 RE到FA的等價變換 0*對應的FA2022/10/10234.3.1 RE到FA的等價變換 02022/10/12244.3.1 RE到FA的等價變換 定理 4-1 RE表示的語言是RL。證明：施歸納于正則表達式中所含的運算符的個數n，證明對于字母表上的任意正則表達式r，存在FA M，使得L(M) = L(r) 。M恰有一個終止狀態。M在終止狀態下不作任何移動。 2022/10/10244.3.1 RE到FA的等價變換 定2022/10/12254.3.1 RE到FA的等價變換 n=0 r=r= r=a 2022/10/1

13、0254.3.1 RE到FA的等價變換 n2022/10/12264.3.1 RE到FA的等價變換 設結論對于n=k時成立，此時有如下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的等價變換 設2022/10/1227n=k+1 r=r1+r2取q0，fQ1Q2，令M=(Q1Q2q0，f，q0，f) (q0，)=q01，q02； 對qQ1，a，(q，a)=1(q，a); 對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的等價變換 n=k+1 r=r1+r2 2022/10/10284.3.1 RE到FA的等價變換 n2022/10/12294.3.1 RE到FA的等價變換 M=(Q1Q2，q01，f2) 對qQ1-f1，a(q，a)=1(q，a)；對qQ2-f2，a(q，a)=2(q，a)； (f1，)=q022022/10/10294.3.1 RE到FA的等價變換 M2022/10/12304.3.1 RE到FA的等價變換 r=r1r2 2022/10/10304.3.1 RE到FA的等價變換 r2022/1

15、0/12314.3.1 RE到FA的等價變換 M=(Q1q0，f，q0，f)其中q0，fQ1，定義為 對qQ1-f1，a，(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。2022/10/10314.3.1 RE到FA的等價變換 M2022/10/12324.3.1 RE到FA的等價變換 r=r1* 2022/10/10324.3.1 RE到FA的等價變換 r2022/10/12334.3.1 RE到FA的等價變換 按照定理4-1證明給出的方法構造一個給定RE的等價FA時，該FA有可能含有許多的空移動。可以按照自己對給定RE的“理解”以及對FA的 “理解” “直接地

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

17、.3.2 RL可以用RE表示 計算DFA的每個狀態對應的集合字母表的克林閉包的等價分類，是具有啟發意義的。 這個計算過程難以“機械”地進行。 計算q1到q2的一類串的集合：Rkij 。圖上作業法。2022/10/10364.3.2 RL可以用RE表示 計算2022/10/12374.3.2 RL可以用RE表示定理4-2 RL可以用RE表示。設DFA M=(q1，q2，qn，q1，F)Rkij=x|(qi，x)=qj而且對于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表示圖上作業法 啟示2022/10/10394.3.2 RL可以用RE表示圖上作2022/10/12404.3.2 RL可以用RE表示圖上作業法操作步驟 預處理： 用標記為X和Y的狀態將M“括起來”： 在狀態轉移圖中增加標記為X和Y的狀態，從標記為X的狀態到標記為q0的狀態引一條標記為的弧；從標記為q(qF)的狀態到標記為Y的狀態分別

19、引一條標記為的弧。 去掉所有的不可達狀態。2022/10/10404.3.2 RL可以用RE表示圖上作2022/10/12414.3.2 RL可以用RE表示 對通過步驟(1)處理所得到的狀態轉移圖重復如下操作，直到該圖中不再包含除了標記為X和Y外的其他狀態，并且這兩個狀態之間最多只有一條弧。 并弧 將從q到p的標記為r1，r2，rg并行弧用從q到p的、標記為r1+r2+rg的弧取代這g個并行弧。 2022/10/10414.3.2 RL可以用RE表示 對2022/10/12424.3.2 RL可以用RE表示去狀態1如果從q到p有一條標記為r1的弧，從p到t有一條標記為r2的弧，不存在從狀態p到

20、狀態p的弧，將狀態p和與之關聯的這兩條弧去掉，用一條從q到t的標記為r1r2的弧代替。 去狀態2如果從q到p有一條標記為r1的弧，從p到t有一條標記為r2的弧，從狀態p到狀態p標記為r3的弧，將狀態p和與之關聯的這三條弧去掉，用一條從q到t的標記為r1r3*r2的弧代替。 2022/10/10424.3.2 RL可以用RE表示去狀態2022/10/12434.3.2 RL可以用RE表示去狀態3如果圖中只有三個狀態，而且不存在從標記為X的狀態到達標記為Y的狀態的路，則將除標記為X的狀態和標記為Y的狀態之外的第3個狀態及其相關的弧全部刪除。 2022/10/10434.3.2 RL可以用RE表示去

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

22、.3.2 RL可以用RE表示去掉狀2022/10/12484.3.2 RL可以用RE表示去掉狀態q4。2022/10/10484.3.2 RL可以用RE表示去掉狀2022/10/12494.3.2 RL可以用RE表示合并從標記為q2的狀態到標記為Y的狀態的兩條并行弧。 2022/10/10494.3.2 RL可以用RE表示合并從2022/10/12504.3.2 RL可以用RE表示去掉狀態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表示去掉狀態q1。2022/10/10524.3.2 RL可以用RE表示去掉狀2022/10/12534.3.2 RL可以用RE表示去掉狀態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表示幾點值得注意的問題 如果去狀態的順序不一樣，則得到的RE可能在形式是不一樣，但它們都是等價的。 當DFA的終止狀態都是不可達的時候，狀態轉移圖中必不存在從開始狀態到終止狀態的路。此時，相應的RE為

24、。 不計算自身到自身的弧，如果狀態q的入度為n，出度為m，則將狀態q及其相關的弧去掉之后，需要添加n*m條新弧。 2022/10/10544.3.2 RL可以用RE表示幾點值2022/10/12554.3.2 RL可以用RE表示 對操作的步數施歸納，可以證明它的正確性。推論4-1 正則表達式與FA、正則文法等價，是正則語言的表示模型。2022/10/10554.3.2 RL可以用RE表示 對2022/10/12564.4 正則語言等價模型的總結 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)圖上作業法歸納2022/10/10564.4 正則語言等價模型的總結 A2022/10/