形式語言與自動機(jī)理論--第四章 正則表達(dá)式（第十周）

1、第第4章章 正則表達(dá)式正則表達(dá)式 1.1.正則表達(dá)式的引出正則表達(dá)式的引出2.2.正則表達(dá)式的形式定義正則表達(dá)式的形式定義3.3.正則表達(dá)式與正則表達(dá)式與FAFA等價等價4.4.正則語言等價模型總結(jié)正則語言等價模型總結(jié)5.5.小結(jié)小結(jié)11.正則表達(dá)式的引出正則表達(dá)式的引出產(chǎn)生語言產(chǎn)生語言anbmck|n，m，k1aicnbxam|i0, ,n1, ,m2, ,x為為d和和e組成的串組成的串 的正則文法為的正則文法為AaA|aB|cEBbB|bCCcC|cE cE|bFFdF|eF|aHHaH|a21.正則表達(dá)式的引出正則表達(dá)式的引出接受此語言的接受此語言的NFA M 31.正則表達(dá)式的引出正則

2、表達(dá)式的引出計算集合計算集合 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)= set(C) c=a+b+c*c =a+b+c+41.正則表達(dá)式的引出正則表達(dá)式的引出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+d，e*aa* =a*c+d，e*a+set(I)= set(H)a=a*c+d，e*a+aL(M)= se

3、t(D)set(I) = a+b+c+a*c+d，e*a+a51.正則表達(dá)式的引出正則表達(dá)式的引出根據(jù)集合運(yùn)算的定義，根據(jù)集合運(yùn)算的定義，d，e=de。從而，從而，d，e*=(de)*。這樣可以將這樣可以將L(M)寫成如下形式：寫成如下形式：L(M)= a+b+c+a*c+(de)*a+a 記作：記作：a+b+c+a*c+(d+e)*a+a= aa*bb*cc*+a*cc*(d+e)* aaa* 62. RE的形式定義的形式定義 定義定義4-1：正則表達(dá)式：正則表達(dá)式(regular expression，RE) 是是上的上的RE，它表示語言，它表示語言； 是是上的上的RE，它表示語言，它表示

4、語言； 對于對于 a，a是是上的上的RE，它表示語言，它表示語言a；72. RE的形式定義的形式定義 如果如果r和和s分別是分別是上表示語言上表示語言R和和S的的RE，則：，則： r與與s的的“和和” (r+s)是是上的上的RE，(r+s)表達(dá)的語言表達(dá)的語言為為RS； r與與s的的“乘積乘積” (rs)是是上的上的RE，(rs)表達(dá)的語言表達(dá)的語言為為RS； r的克林閉包的克林閉包(r*)是是上的上的RE，(r*)表達(dá)的語言為表達(dá)的語言為R*。 只有滿足、的才是只有滿足、的才是上的上的RE。82. RE的形式定義的形式定義 例例 4-1 設(shè)設(shè)=0，1 0，表示語言，表示語言0； 1，表示語言

5、，表示語言1； (0+1)，表示語言，表示語言0，1； (01)，表示語言，表示語言01； (0+1)*)，表示語言，表示語言0，1*； (00)(00)*)，表示語言，表示語言0000*；92. RE的形式定義的形式定義 (0+1)*)(0+1)(0+1)*)，表示語言，表示語言0，1+； (0+1)*)000)(0+1)*)，表示，表示0，1上的至少含有上的至少含有3個連續(xù)個連續(xù)0的串組成的語言；的串組成的語言； (0+1)*)0)1)，表示所有以，表示所有以01結(jié)尾的結(jié)尾的0、1字符串組字符串組成的語言；成的語言； (1(0+1)*)0)，表示所有以，表示所有以1開頭，并且以開頭，并且以

6、0結(jié)尾的結(jié)尾的0、1字符串組成的語言。字符串組成的語言。 102. RE的形式定義的形式定義 約定約定 r的正閉包的正閉包r+表示表示r與與(r*)的乘積以及的乘積以及(r*)與與r的乘積：的乘積： r+=(r(r*)=(r*)r) 閉包運(yùn)算的優(yōu)先級最高，乘運(yùn)算的優(yōu)先級次之，閉包運(yùn)算的優(yōu)先級最高，乘運(yùn)算的優(yōu)先級次之，加運(yùn)算加運(yùn)算“+”的優(yōu)先級最低。所以，在意義明確時，的優(yōu)先級最低。所以，在意義明確時，可以省略其中某些括號?？梢允÷云渲心承├ㄌ?。 (0+1)*)000)(0+1)*)=(0+1)*000(0+1)* 112. RE的形式定義的形式定義 (0+1)*)(0+1)(0+1)*)=(0

7、+1)*(0+1)(0+1)* 在意義明確時，在意義明確時，RE r表示的語言記為表示的語言記為L(r)，也可，也可以直接地記為以直接地記為r。 加、乘、閉包運(yùn)算均執(zhí)行左結(jié)合規(guī)則。加、乘、閉包運(yùn)算均執(zhí)行左結(jié)合規(guī)則。122. RE的形式定義的形式定義 定義定義4-2：正則表達(dá)式相等：正則表達(dá)式相等(equivalence)r、s是字母表是字母表上的一個上的一個RE，如果，如果L(r)=L(s)，則稱，則稱r與與s相等，相等，記作記作r=s 。相等也稱為相等也稱為等價。等價。幾個基本結(jié)論幾個基本結(jié)論 結(jié)合律：結(jié)合律：(rs)t=r(st) (r+s)+t=r+(s+t) 分配律：分配律：r(s+t

8、)=rs+rt (s+t)r=sr+tr132. RE的形式定義的形式定義 交換律：交換律：r+s=s+r。 冪等律：冪等律：r+r=r。 加法運(yùn)算零元素：加法運(yùn)算零元素：r+=r。 乘法運(yùn)算單位元：乘法運(yùn)算單位元：r=r=r。 乘法運(yùn)算零元素：乘法運(yùn)算零元素：r=r=。 L()=。 L()=。 L(a)=a。 142. RE的形式定義的形式定義 L(rs)=L(r)L(s)。 L(r+s)=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

9、=s。152. RE的形式定義的形式定義 L(rn)=(L(r)n 。 rnrm=rn+m 。一般地，一般地， r+r，(rs)n rnsn，rssr。定義定義4-3：冪：冪 r是字母表是字母表上的上的RERE，r的的n次次冪冪定義為定義為 r0=。 rn=rn-1r。 162. RE的形式定義的形式定義 例例 4-2 設(shè)設(shè)=0，100表示語言表示語言00；(0+1)*00(0+1)*表示所有的至少含兩個連續(xù)表示所有的至少含兩個連續(xù)0的的0、1串組成的語言；串組成的語言；(0+1)*1(0+1)9表示所有的倒數(shù)第表示所有的倒數(shù)第10個字符為個字符為1的串組成的語言；的串組成的語言；172. R

10、E的形式定義的形式定義 L(0+1)*011)=x|x是以是以011結(jié)尾的結(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的開頭字符與尾字的開頭字符與尾字符相同符相同。183. RE與與FA等價等價 定義定義4-4：正則表達(dá)式：正則表達(dá)式r稱為與稱為與FA M等價，如果等價，如果L(r)=L(M)。從開始狀態(tài)出發(fā)，根據(jù)狀態(tài)之間按照轉(zhuǎn)移所確定的從開始狀態(tài)出發(fā)，根據(jù)狀態(tài)之間按照轉(zhuǎn)移所確定的后繼關(guān)系，依次計算出所給后繼關(guān)系，依次計算出所給FA的各個狀態(tài)的各個狀態(tài)q對應(yīng)的對應(yīng)的set(q)

11、，并且最終得到相應(yīng)的，并且最終得到相應(yīng)的FA接受的語言的接受的語言的RE表表示。示。 尋找一種比較尋找一種比較“機(jī)械機(jī)械”的方法，使得計算機(jī)系統(tǒng)能的方法，使得計算機(jī)系統(tǒng)能夠自動完成夠自動完成FA與與RE之間的轉(zhuǎn)換。之間的轉(zhuǎn)換。 193.1 RE到到FA的等價變換的等價變換 0對應(yīng)的對應(yīng)的FA0101對應(yīng)的對應(yīng)的FAFA203.1 RE到到FA的等價變換的等價變換 0+1對應(yīng)的對應(yīng)的FA213.1 RE到到FA的等價變換的等價變換 0*對應(yīng)的對應(yīng)的FA223.1 RE到到FA的等價變換的等價變換 定理定理 4-1 RERE表示的語言是表示的語言是RLRL。證明思路：證明思路：施歸納于正則表達(dá)式中

12、所含的運(yùn)算符的個數(shù)施歸納于正則表達(dá)式中所含的運(yùn)算符的個數(shù)n，證，證明對于字母表明對于字母表上的任意正則表達(dá)式上的任意正則表達(dá)式r，存在，存在FA M，使得使得L(M) = L(r) 。M恰有一個終止?fàn)顟B(tài)。恰有一個終止?fàn)顟B(tài)。M在終止?fàn)顟B(tài)下不作任何移動。在終止?fàn)顟B(tài)下不作任何移動。 構(gòu)造正則表達(dá)式對應(yīng)的構(gòu)造正則表達(dá)式對應(yīng)的FA證明構(gòu)造的證明構(gòu)造的FA與與RE等價等價此處僅給出各種情況下此處僅給出各種情況下FA的構(gòu)造方法。的構(gòu)造方法。233.1 RE到到FA的等價變換的等價變換 r=r= r=a 243.1 RE到到FA的等價變換的等價變換 對于已有正則表達(dá)式對于已有正則表達(dá)式r1與與r2對應(yīng)的對應(yīng)的

13、FA：M1=(Q1，1，q01，f1)M2=(Q2，2，q02，f2)L(M1)=L(r1)，L(M2)=L(r2) 。Q1Q2=。 由于正則表達(dá)式的運(yùn)算包括加、乘和冪集，所以由于正則表達(dá)式的運(yùn)算包括加、乘和冪集，所以分別給出分別給出r=r1+r2； r=r1r2； r=r1*情況下情況下FA的機(jī)械化構(gòu)造方的機(jī)械化構(gòu)造方法法253.1 RE到到FA的等價變換的等價變換 第一種情況：第一種情況：r=r1+r2取取q0，f Q1Q2，令，令M=(Q1Q2q0，f，q0，f) (q0，)=q01，q02； 對對 qQ1，a，(q，a)=1(q，a); 對對 qQ2，a，(q，a)=2(q，a)； (

14、f1，)=f； (f2，)=f。 263.1 RE到到FA的等價變換的等價變換 273.1 RE到到FA的等價變換的等價變換 M=(Q1Q2，q01，f2) 對對 qQ1-f1，a(q，a)=1(q，a)； 對對 qQ2-f2，a(q，a)=2(q，a)； (f1，)=q0228第二種情況：第二種情況：r=r1r2 3.1 RE到到FA的等價變換的等價變換 293.1 RE到到FA的等價變換的等價變換 M=(Q1q0，f，q0，f)其中其中q0，f Q1，定義，定義為為 對對 qQ1-f1，a,(q，a)=1(q，a)。 (f1，)=q01，f。 (q0，)=q01，f。30第三種情況：第三種

15、情況：r=r1* 3.1 RE到到FA的等價變換的等價變換 313.1 RE到到FA的等價變換的等價變換 按照以上方法構(gòu)造一個給定按照以上方法構(gòu)造一個給定RERE的等價的等價FA時，該時，該FA有可能含有許多的空移動。有可能含有許多的空移動?？梢园凑兆约簩o定可以按照自己對給定RERE的的“理解理解”以及對以及對FA的的 “理解理解” “直接地直接地”構(gòu)造出一個比較構(gòu)造出一個比較“簡單簡單”的的FA。定理證明中所給的方法是機(jī)械的。由于定理證明中所給的方法是機(jī)械的。由于“直接地直接地”構(gòu)造出的構(gòu)造出的FA的正確性依賴于構(gòu)造者的的正確性依賴于構(gòu)造者的“理解理解”，所以它的正確性缺乏有力的保證。所以

16、它的正確性缺乏有力的保證。 323.1 RE到到FA的等價變換的等價變換 例例 4-3 構(gòu)造與構(gòu)造與 (0+1)*0+(00)*等價的等價的FA。解答：解答：設(shè)設(shè)r1= (0+1)*0 M1 r2=(00)* M2 r= r1+ r2 M333.1 RE到到FA的等價變換的等價變換 r2=(00)*設(shè)設(shè)r3=00,則則r2=（r3）*343.1 RE到到FA的等價變換的等價變換 r3=00；設(shè)設(shè)r4=0則則r3=r4r4r3對應(yīng)的對應(yīng)的FA M3為：為：353.1 RE到到FA的等價變換的等價變換 到目前為止，得到的自動機(jī)如下圖所示：363.1 RE到到FA的等價變換的等價變換 r1= (0+

17、1)*0設(shè)設(shè)r5=1則則r1=（r4+r5）*r4373.1 RE到到FA的等價變換的等價變換 最終轉(zhuǎn)換完成的FA如下圖所示：383.2 RL可以用可以用RE表示表示 探討如何從給定的探討如何從給定的DFADFA構(gòu)造等價的正則表達(dá)式。構(gòu)造等價的正則表達(dá)式。計算計算DFA的每個狀態(tài)對應(yīng)的集合的每個狀態(tài)對應(yīng)的集合字母表的克林字母表的克林閉包的等價分類，是具有啟發(fā)意義的。閉包的等價分類，是具有啟發(fā)意義的。 這個計算過程難以這個計算過程難以“機(jī)械機(jī)械”地進(jìn)行。地進(jìn)行。 計算計算qi到到qj的一類串的集合：的一類串的集合：Rkij 。圖上作業(yè)法。圖上作業(yè)法。393.2 RL可以用可以用RE表示表示定理定

18、理4-2 RL可以用可以用RE表示。表示。構(gòu)造與構(gòu)造與FA等價的等價的RE403.2 RL可以用可以用RE表示表示圖上作業(yè)法操作步驟圖上作業(yè)法操作步驟 預(yù)處理：預(yù)處理： 用標(biāo)記為用標(biāo)記為X和和Y的狀態(tài)將的狀態(tài)將M“括起來括起來”： 在狀態(tài)轉(zhuǎn)移圖中增加標(biāo)記為在狀態(tài)轉(zhuǎn)移圖中增加標(biāo)記為X和和Y的狀態(tài)，從標(biāo)記的狀態(tài)，從標(biāo)記為為X的狀態(tài)到標(biāo)記為的狀態(tài)到標(biāo)記為q0的狀態(tài)引一條標(biāo)記為的狀態(tài)引一條標(biāo)記為的?。坏幕。粡臉?biāo)記為從標(biāo)記為q(qF)的狀態(tài)到標(biāo)記為的狀態(tài)到標(biāo)記為Y的狀態(tài)分別引的狀態(tài)分別引一條標(biāo)記為一條標(biāo)記為的弧。的弧。 去掉所有的不可達(dá)狀態(tài)。去掉所有的不可達(dá)狀態(tài)。413.2 RL可以用可以用RE表示表示

19、 對通過步驟對通過步驟(1)處理所得到的狀態(tài)轉(zhuǎn)移圖重復(fù)如下處理所得到的狀態(tài)轉(zhuǎn)移圖重復(fù)如下操作，直到該圖中不再包含除了標(biāo)記為操作，直到該圖中不再包含除了標(biāo)記為X和和Y外的其外的其他狀態(tài)，并且這兩個狀態(tài)之間最多只有一條弧。他狀態(tài)，并且這兩個狀態(tài)之間最多只有一條弧。 并弧并弧 將從將從q到到p的標(biāo)記為的標(biāo)記為r1，r2，rg并行弧用從并行弧用從q到到p的、標(biāo)記為的、標(biāo)記為r1+r2+rg的弧取代這的弧取代這g個并行弧。個并行弧。 423.2 RL可以用可以用RE表示表示去狀態(tài)去狀態(tài)1 1如果從如果從q q到到p p有一條標(biāo)記為有一條標(biāo)記為r r1 1的弧，從的弧，從p p到到t t有一條標(biāo)記有一條標(biāo)

20、記為為r r2 2的弧，不存在從狀態(tài)的弧，不存在從狀態(tài)p p到狀態(tài)到狀態(tài)p p的弧，將狀態(tài)的弧，將狀態(tài)p p和和與之關(guān)聯(lián)的這兩條弧去掉，用一條從與之關(guān)聯(lián)的這兩條弧去掉，用一條從q q到到t t的標(biāo)記為的標(biāo)記為r r1 1r r2 2的弧代替。的弧代替。 433.2 RL可以用可以用RE表示表示去狀態(tài)去狀態(tài)2 2如果從如果從q q到到p p有一條標(biāo)記為有一條標(biāo)記為r r1 1的弧，從的弧，從p p到到t t有一條標(biāo)記有一條標(biāo)記為為r r2 2的弧，從狀態(tài)的弧，從狀態(tài)p p到狀態(tài)到狀態(tài)p p標(biāo)記為標(biāo)記為r r3 3的弧，將狀態(tài)的弧，將狀態(tài)p p和與之關(guān)聯(lián)的這三條弧去掉，用一條從和與之關(guān)聯(lián)的這三條弧

21、去掉，用一條從q q到到t t的標(biāo)記為的標(biāo)記為r r1 1r r3 3* *r r2 2的弧代替。的弧代替。 443.2 RL可以用可以用RE表示表示去狀態(tài)去狀態(tài)3 3如果圖中只有三個狀態(tài)，而且不存在從標(biāo)記為如果圖中只有三個狀態(tài)，而且不存在從標(biāo)記為X的狀的狀態(tài)到達(dá)標(biāo)記為態(tài)到達(dá)標(biāo)記為Y的狀態(tài)的路，則將除標(biāo)記為的狀態(tài)的路，則將除標(biāo)記為X的狀態(tài)的狀態(tài)和標(biāo)記為和標(biāo)記為Y的狀態(tài)之外的第的狀態(tài)之外的第3個狀態(tài)及其相關(guān)的弧全個狀態(tài)及其相關(guān)的弧全部刪除。部刪除。 453.2 RL可以用可以用RE表示表示 從標(biāo)記為從標(biāo)記為X的狀態(tài)到標(biāo)記為的狀態(tài)到標(biāo)記為Y的狀態(tài)的弧的標(biāo)記為的狀態(tài)的弧的標(biāo)記為所求的正則表達(dá)式。如果

22、此弧不存在，則所求的正則所求的正則表達(dá)式。如果此弧不存在，則所求的正則表達(dá)式為表達(dá)式為。 463.2 RL可以用可以用RE表示表示例例 4-4 求圖求圖4-14所示的所示的DFA等價的等價的RE 。473.2 RL可以用可以用RE表示表示預(yù)處理。預(yù)處理。483.2 RL可以用可以用RE表示表示去掉狀態(tài)去掉狀態(tài)q3。493.2 RL可以用可以用RE表示表示去掉狀態(tài)去掉狀態(tài)q4。503.2 RL可以用可以用RE表示表示合并從標(biāo)記為合并從標(biāo)記為q2的狀態(tài)到標(biāo)記為的狀態(tài)到標(biāo)記為Y的狀態(tài)的兩條并行的狀態(tài)的兩條并行弧。弧。 513.2 RL可以用可以用RE表示表示去掉狀態(tài)去掉狀態(tài)q0。523.2 RL可以

23、用可以用RE表示表示并弧。并弧。 533.2 RL可以用可以用RE表示表示去掉狀態(tài)去掉狀態(tài)q1。543.2 RL可以用可以用RE表示表示去掉狀態(tài)去掉狀態(tài)q2。1*0(11*0)*0(00*111*0+00*10+11*0)(11*0)*0)*(00*+00*1)就是所求。就是所求。 553.2 RL可以用可以用RE表示表示幾點(diǎn)值得注意幾點(diǎn)值得注意的問題的問題 如果去狀態(tài)的順序不一樣，則得到的如果去狀態(tài)的順序不一樣，則得到的RERE可能在形式可能在形式是不一樣，但它們都是等價的。是不一樣，但它們都是等價的。 當(dāng)當(dāng)DFADFA的終止?fàn)顟B(tài)都是不可達(dá)的時候，狀態(tài)轉(zhuǎn)移圖的終止?fàn)顟B(tài)都是不可達(dá)的時候，狀態(tài)轉(zhuǎn)移圖中必不存在從開始狀態(tài)到終止?fàn)顟B(tài)的路。中必不存在從開始狀態(tài)到終止?fàn)顟B(tài)的路。此時，相應(yīng)此時，相應(yīng)的的RERE為為。 不計算自身到自身的弧，如果狀態(tài)不計算自身到自身的弧，如果狀態(tài)q q的入度為的入度為n n，出，出度為度為m m，則將狀態(tài)，則將狀態(tài)q q及其相關(guān)的弧去掉之后，需要添加及其相關(guān)的弧去掉之后，需要添加n n* *m m條新弧。條新弧。 563.2 RL可以用可以用RE表示表示 對操作的步數(shù)施歸納，可以證明它的正確性。對操作的步數(shù)施歸納，可以證明它的正確性。推論推論4-1 正則表達(dá)式與正