形式語(yǔ)言與自動(dòng)機(jī)：第05講-正則表達(dá)式與正則語(yǔ)言

1、形式語(yǔ)言與自動(dòng)機(jī)Formal Languages and Automata Theory第四章 正則表達(dá)式與正則語(yǔ)言第四章 正則表達(dá)式正則表達(dá)式的引入正則表達(dá)式的定義及性質(zhì)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與正則文法等價(jià)正則語(yǔ)言等價(jià)描述模型總結(jié)正則表達(dá)式的引入有窮自動(dòng)機(jī)描述模型：例：設(shè)正則語(yǔ)言： anbmck | n, m, k1 aicnbxam | i0, n 1, m 2, x 是由 d 和 e 組成的字符串 正則表達(dá)式的引入 FA 各狀態(tài)對(duì)輸入字符串的存儲(chǔ)功能：由于,所以,正則表達(dá)式的引入正則語(yǔ)言：正則表達(dá)式：r = a+ b+ c+ + a*c+ b( d + e )*a+ a =

2、 a a*bb*cc* + a*cc*( d + e )*aaa*第四章 正則表達(dá)式正則表達(dá)式的引入正則表達(dá)式的定義及性質(zhì)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與正則文法等價(jià)正則語(yǔ)言等價(jià)描述模型總結(jié)定義4-1：設(shè)字母表為 ，正則表達(dá)式遞歸定義如下：正則表達(dá)式的定義及性質(zhì)例：設(shè) = 0，1 ， 中部分正則表達(dá)式及其對(duì)應(yīng)語(yǔ)言如下：正則表達(dá)式的定義及性質(zhì)定義4 - 2：設(shè) r 是字母表上的正則表達(dá)式，r 的 n 次冪定義為：滿足性質(zhì)：L（r n）= （L（r）n,rn r m = r n + m, n, m0正則表達(dá)式的定義及性質(zhì)表達(dá)式簡(jiǎn)化約定： - 減少括號(hào)1、r 的正閉包：2、運(yùn)算符的優(yōu)先級(jí)： 閉

3、包運(yùn)算 乘運(yùn)算 加運(yùn)算 正則表達(dá)式的定義及性質(zhì)(0+1)*)000)(0+1)*) = (0+1)*000(0+1)*(0+1)*)(0+1)(0+1)*) = (0+1)*(0+1)(0+1)*表達(dá)式的簡(jiǎn)化約定：3、意義明確時(shí)，正則表達(dá)式 r 表示的語(yǔ)言記為 L（r）， 也可直接記為 r。4、無(wú)擴(kuò)號(hào)說(shuō)明時(shí)，加、乘、閉包運(yùn)算執(zhí)行左結(jié)合規(guī)則。 例： R1 R2 R3 = （R1 R2）R3 R1 R2 R3 = （R1 R2）R3 正則表達(dá)式的定義及性質(zhì)定義4 - 3： 設(shè) r, s 分別為字母表 上的正則表達(dá)式 ，如果 L ( r ) = L ( s ), 則稱表達(dá)式 r 與 s 相等（或等價(jià)

4、），記作 r = s。正則表達(dá)式的定義及性質(zhì)例：設(shè) = 0，1 ，上正則表達(dá)式以及其表示的語(yǔ)言如下：1、L ( 00 )2、L( 0+1 )* 00 (0+1)*) 3、L( 0+1 )*1 ( 0+1 )9)4、L（( 0+1 )*011）5、 L ( 0+1+2+ )6、 L ( 0*1*2* )7、 L ( 1 ( 0+1 )* 1 + 0 ( 0+1 )*0 )正則表達(dá)式表示的正則語(yǔ)言：正則表達(dá)式的定義及性質(zhì)例：設(shè) = 0，1 ，上正則表達(dá)式以及其表示的語(yǔ)言如下：1、L ( 00 ) =2、L( 0+1 )* 00 (0+1)*) = 3、L( 0+1 )*1 ( 0+1 )9) =4

5、、L（( 0+1 )*011）=5、 L ( 0+1+2+ ) =6、 L ( 0*1*2* ) =7、 L ( 1 ( 0+1 )* 1 + 0 ( 0+1 )*0 ) =正則表達(dá)式表示的正則語(yǔ)言：正則表達(dá)式的定義及性質(zhì) 00 。 x | x 是至少含兩個(gè)連續(xù) 0 的串 x | x 是倒數(shù)第十個(gè)字符為 1 的串 x | x 是 011 結(jié)尾的串 。 0n 1m 2k | n, m, k1 。 0n 1m 2k | n, m, k0 。習(xí)題：p.153, 2. 理解正則表達(dá)式正則表達(dá)式的定義及性質(zhì)習(xí)題：p.153, 1. 寫(xiě)出下列語(yǔ)言的表達(dá)式正則表達(dá)式的定義及性質(zhì)可以證明，字母表 上正則表達(dá)式

6、 r, t, s 及相關(guān)語(yǔ)言滿足以下等式：正則表達(dá)式的定義及性質(zhì)例1- 證16式：L ( (r*) )* = L (r)*，其對(duì)應(yīng)語(yǔ)言集合 ( R* )* = R*。證：施歸納于集合 R 乘積的個(gè)數(shù)，求證 （ R* )n = R* ( n 0 )?；A(chǔ)語(yǔ)句： 設(shè) n = 0，1，（ R* )0 = ，（ R* )1 = R*，結(jié)論成立。歸納語(yǔ)句：設(shè) n 1,（ R* )n = R* 結(jié)論成立，證 ( R* )n+1 = R* 時(shí)結(jié)論成立 ( R* )n+1 = ( R*)n R* = R*R*由歸納假設(shè) = , R, R2, R3, , R, R2, R3, = , R, R2, R3, =

7、R*正則表達(dá)式的定義及性質(zhì)由歸納原理可知，對(duì)任意整數(shù) n, 有 ( R* )n = R*; 因此，有， ( R* )* = ( R* )0，( R* )1，( R* )2， ( R* )n， = ，R* = R* 證畢。例2- 證 ( 17 ) 式：L ( r s ) = L ( r + s )設(shè)A、B為表達(dá)式 r、s 對(duì)應(yīng)的正則集合，利用下列集合性質(zhì)： ( 1 ) 若A B 和 C D，則 AC BD ； ( 2 ) An A，n 0 （3） A A B ( 4 ) A B A （5） 若 A B，則 A B ( 6 )（A） = A A = A正則表達(dá)式的定義及性質(zhì)證 i : （ A B

8、） （ A B ） 由 A A B 和（5）有： A （A B ) 和 B （ AB ) 由 （1）有： A B ( A B ) （ A B ) 由（ 6）有： A B ( A B ) 由（5） 有：（A B ) ( ( A B ) ) 由（6 ）有：（A B ) ( A B )（ i 得證 )證 ii：（ A B ） （ A B ） 由（2）有： A A ， B B 由（3）有： A A B 由（4）有： B A B 由(2)(3)(4)和傳遞率： A B A B A B = A B 由（5）有： （ A B ） （A B ） 由于集合（A B ） 的正則表達(dá)式為 ( r*s* ) *； 集

9、合（A B） 的正則表達(dá)式為 ( r + s ) * ； 所以有： ( r*s* ) * = ( r + s )* 由 i 和 ii 得： （A* B* ）* =（A B）* 正則表達(dá)式的定義及性質(zhì)（ii 得證）（證畢）習(xí)題：p.154, 4. 正則表達(dá)式的定義及性質(zhì)第四章 正則表達(dá)式正則表達(dá)式的引入正則表達(dá)式的定義及性質(zhì)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與正則文法等價(jià)正則語(yǔ)言等價(jià)描述模型總結(jié)定義4-4： 稱正則表達(dá)式 r 與自動(dòng)機(jī) FA 等價(jià)，如果有 L（r）= L（M）。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)定理 4-1： 正則表達(dá)式表示的語(yǔ)言是正則語(yǔ)言。證明思路： 對(duì)字母

10、表 上任意正則表達(dá)式 r，構(gòu)造相應(yīng)的 FA M，使得 L（r）= L（M）； 1、歸納證明：施歸納于正則表達(dá)式運(yùn)算符 (+、連接、*) 的個(gè)數(shù) 2、構(gòu)造 FA M 的終止?fàn)顟B(tài)。 基礎(chǔ)： 設(shè)正則表達(dá)式運(yùn)算符的個(gè)數(shù) n = 0，構(gòu)造 FA 存在以下三種情況： r =：有 - NFA 滿足要求。 r = ：有 - NFA 滿足要求。 r = a：有 - NFA 滿足要求。 結(jié)論對(duì) n = 0 成立。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)1、對(duì)于 r = r1 + r2，構(gòu)造相應(yīng)-NFA。 假設(shè) M1 = ， M2 = ，使得 L（M1）= L（r1），L（M2）= L（r2）；并設(shè) Q1 Q2 = 。 構(gòu)造 F

11、A M = , 其中 q0, f Q1 Q2， 定義：1）( q0, ) = q01, q02 ， 2）對(duì) q Q1 - f1 ，a ：( q, a ) = 1 ( q, a ) ； 對(duì) q Q2 - f2 ，a ：( q, a ) = 2 ( q, a ) ； 3） ( f1, ) = f ； ( f2, ) = f 由于1( f1, ) = 2( f2, ) = 歸納：設(shè)結(jié)論對(duì)運(yùn)算符個(gè)數(shù)為 n k ( k0 )的表達(dá)式成立，證當(dāng) n = k + 1 時(shí)，結(jié)論仍然成立。添加運(yùn)算符時(shí), 存在 r1 + r2, r1r2, r* 三種情況。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)1、構(gòu)造與表達(dá)式 r = r1

12、 + r2 等價(jià)的-NFA 的圖示：正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)1、對(duì)于 r = r1 + r2，求證：L（r1 + r2）= L（M）。由歸納假設(shè)： L（r1）= L（M1）， L（r2）= L（M2）； 由正則表達(dá)式性質(zhì)： L ( r1 + r2 ) = L ( r1 ) L ( r2 ) = L ( M1 ) L ( M2 )需證： L（M1） L（M2）= L（M） 。 （ “” ）設(shè) x L（ M1 ） L（ M2 ），應(yīng)有 x L（ M1 ）或 x L（ M2 ），假設(shè) x L（M1），即，1 ( q01, x ) = f1 ，于是有：即有，x L ( M

13、)同理可證： x L ( M2 ) 時(shí)，有 x L（ M ）。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)設(shè) x L（M），即， ( q0, x ) = f ；由 M 定義：證： L（M）= L（M1） L（M2） 。 （ “” ）1、求證： L（M）= L（r1+r2） 。由于已設(shè) ( q0, x ) f 成立, 并且, 有 f = 1 ( f1, ) = 2 ( f2, )必有，1( q01, x ) = f1 ( x L( M1 ) 或者 2 ( q02, x) = f2 ( x L(M2) )故有， x L（M1） x L（M2）。 （“ M 與 r 等價(jià) ” 證畢 ）正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)例4：

14、給定正則表達(dá)式 r1 = 01* ，r2 = ( 01 )*，以及與其等價(jià)的 FA M1、M2 如下，構(gòu)造與表達(dá)式 r = r1 + r2 等價(jià)的- NFA Mq02q2201q12q0110M1M21q0q12q02q2201q010qf解：正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)2、對(duì)于 r = r1r2，構(gòu)造相應(yīng)-NFA。 假設(shè) M1 = ，M2 = ，使得 L（M1）= L（r1），L（M2）= L（r2）；并設(shè) Q1 Q2 = 。 構(gòu)造 FA M = , 定義：1）對(duì) q Q1 - f1 ，a ，( q, a ) = 1 ( q, a ) ； 2）對(duì) q Q2， a ，( q, a ) = 2 (

15、 q, a ) ； 3）( f1, ) = q02 ； 設(shè) ( f1, ) = ( f2, ) = 。歸納：設(shè)結(jié)論對(duì)運(yùn)算符個(gè)數(shù)為 n k ( k0 )的表達(dá)式成立，證 n= k+ 1 時(shí)結(jié)論仍然成立。由正則表達(dá)式定義, 存在 r1 + r2, r1r2, r* 三種情況。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)2、構(gòu)造與表達(dá)式 r = r1r2 等價(jià)的-NFA 的圖示：設(shè) x L（M1）L（M2）， x = x1x2，有 x1 L（M1）并且 x2 L（M2 )；由于 q Q1, a, 由定義( q, a ) = 1 ( q, a )故有( q01, x1 ) = 1 ( q01, x1 ) = f1 ；由

16、于 qQ2, a , 由定義( q, a ) = 2 ( q, a )故有( q02, x2 ) = 2 ( q02, x2 ) = f2 。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)2、對(duì)于 r = r1r2 ，求證：L（r1 r2）= L（M）。由歸納假設(shè)有： L ( r1 ) = L ( M1 )， L ( r2 ) = L ( M2 )；由正則表達(dá)式性質(zhì)： L ( r1 r2 ) = L ( r1 ) L ( r2 ) = L ( M1 ) L ( M2 )只需證： L（ M1 ）L（ M2 ）= L（ M ） 。 （ “”）故有，x L（M）。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)2、求證： L（M）= L（r

17、1 r2）。 即證： L（M）= L（M1）L（M2）。 （ “” ）其中, ( q01, x1 ) = f1 , 即有，x1 L（M1）； ( f1, ) = q02 ( q02, x2 ) = f2 , 即有，x2 L（M2）；從而， x L（M ） L（M1）L（M2）。綜上所述，L（M）= L（M1） L（M2）成立M 與 r 等價(jià) 證畢。設(shè) x L（M），即有，( q01, x ) = f2 ，并且 x = x1 x2，使得，例5：設(shè) r1 = ( bc )* ，r2 = ( ba )* ；識(shí)別它們的 FA 分別為 M1 和 M2，構(gòu)造與 r = r1r2 等價(jià)的- NFA M。 q

18、02q22M2abq01q12cbM1q02q22M2abq12cb sq013、對(duì)于 r = r1*，構(gòu)造相應(yīng)-NFA。 由歸納假設(shè)： M1 = ， 使得 L（M1 ）= L（r1） 構(gòu)造 FA M = , 其中，q0, f Q1。 定義：對(duì) q Q1 - f1 ，a ， 1） ( q, a ) = 1 ( q, a ) ； 2） ( q0, ) = q01, f ； 3） ( f1, ) = q01，f 。歸納：設(shè)結(jié)論對(duì)運(yùn)算符個(gè)數(shù)為 n k ( k0 ) 的表達(dá)式成立，證 n = k + 1 時(shí)結(jié)論仍然成立。由正則表達(dá)式定義, 存在 r1 + r2, r1r2, r* 三種情況。正則表達(dá)式

19、與有限自動(dòng)機(jī)等價(jià)3、構(gòu)造與表達(dá)式 r = r1* 等價(jià)的-NFA 的圖示：正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)3、對(duì)于 r = r1*，求證：L ( M ) = L（M1）*證: L ( M ) ( L ( M1 ) )*設(shè) x L（ M ），如果 x =, 由克林閉包定義，顯然有， x = ( L ( M1 ) )*；如果 x , 則有 x = x1x2x3xn ( n1 ) 推導(dǎo)過(guò)程見(jiàn)右式。表明： x1, x2, x3, x n L ( M1 )于是有： x = x1x2x3xn ( L ( M1 ) )*同理可證：( L ( M1 ) )* L ( M )例6：設(shè)表達(dá)式

20、r1 = (ac)*ba 的 FA M1如圖所示，構(gòu)造與 r = ( r1 )* = ( ac *ba )* 等價(jià)的 - NFA M。q2 bq01q02aacq12q22q2 q0bq01q02aacq12q22qf例7：構(gòu)造與表達(dá)式 ( 0+1 )*0 + ( 00 )* 等價(jià)的 FA。幾點(diǎn)說(shuō)明：1、由 “+”、“連接”、“*” 的證明過(guò)程可知，結(jié)論對(duì) 上任意正則表達(dá)式成立，即，“對(duì)于任意正則表達(dá)式，都存在一個(gè)等價(jià)的- NFA”。2、綜合第三章結(jié)論：任意 NFA 均有與之等價(jià)的 DFA；有， RE |=| - NFA |=| NFA |=| DFA 。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)例： 設(shè) r

21、1 = 01* ，r2 = ( 01 )*，求 r = r1 + r2 的 DFA M。 解： 1、構(gòu)造識(shí)別 r1 和 r2 的 FA M1 和 M2；正則表達(dá)式與有限自動(dòng)機(jī)的等價(jià)性q02q2201q11q0110M1M21q010q0q11q02q2201qf2、構(gòu)造識(shí)別 r = r1 + r2 的 DFA M 的狀態(tài)圖與狀態(tài)表：其中，始態(tài)( q0,) = q01, q02 ；終態(tài)( q11, q02 ,) = qf 。3、畫(huà)出 DFA M 的狀態(tài)圖：令 p0= q01, q02，p1= q11, q22， p2= q11, q02，p3= q22 ， p4= q11 ， p5= q02 。

22、p0p1p2p3p4p50001 111q01, q02q11, q22q11, q02 q22 q11 q02 2、由 NFA 求 DFA 算法給出DFA M 的狀態(tài)表： q22 q02 終態(tài) q11 q11 終態(tài) q02 q22 q11 q22 q11, q02 終態(tài) q11, q02 q11, q22 終態(tài) q11, q22 q01, q02 始態(tài)10輸入字符列狀態(tài)列狀態(tài)說(shuō)明等價(jià)證明與轉(zhuǎn)換算法： 給定有窮自動(dòng)機(jī) FA，利用圖解法求相應(yīng)等價(jià)的正則表達(dá)式。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)定義4-4： 稱正則表達(dá)式 r 與自動(dòng)機(jī) FA 等價(jià)，如果有 L（r）= L（M）。2-1、 “圖解法”：1、預(yù)

23、處理：刪去 M 中所有不可達(dá)狀態(tài)，并在 M 的始態(tài) q0, 和終態(tài) f1, 兩端分別添加用-連接弧連接的狀態(tài) X，Y，將 M 括起來(lái)；變換 1 - 去 “并” ?。?、弧變換：對(duì)預(yù)處理后的狀態(tài)圖重復(fù)進(jìn)行以下變換，直至圖中除了 X 和 Y 以外，不再含有其它狀態(tài)； 最后，X 和 Y之間最多只有一條弧。 正則表達(dá)式與有限自動(dòng)機(jī)等價(jià) DFA/RE圖解法3、結(jié)束算法：當(dāng) X，Y 之間唯一存在一條弧時(shí)，弧上的標(biāo)記則為所求的正則表達(dá)式；當(dāng)弧不存在時(shí)，則表達(dá)式為 。變換 2 - 去 “連接” 弧 ： 變換 3 - 去“連接”弧和“ * ” 弧 ： 變換 4 - 去最終剩余的獨(dú)立狀態(tài)：如果圖中只剩下三個(gè)狀態(tài)

24、X、Y、Z，并且， X 與 Y 之間不存在任何路徑，則可刪去除 X，Y以外的第三個(gè)狀態(tài) Z 以及與其相關(guān)弧。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)例8：設(shè) M = 如下，求與其相應(yīng)正則表達(dá)式。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)步驟 1：用新添狀態(tài) X、Y及相關(guān)-連接弧，將 DFA 括起來(lái)。步驟 2：刪除所有不可達(dá)狀態(tài)。本狀態(tài)圖中無(wú)不可達(dá)狀態(tài)，本步驟不執(zhí)行。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)步驟 3：去除狀態(tài) q3 ：“連接” 弧與 “*” 弧。步驟 4：去除狀態(tài) q4 ：“連接”弧正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)步驟 5：去除 q2 到 Y 的 “并行” 弧。步驟 6：去除狀態(tài) q0 ：“*”弧和 “

25、連接” 弧。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)步驟 7：去除 q1 到 q2 之間的 “并行” 弧。步驟 8：去除狀態(tài) q1 ：“連接” 弧與 “*” 弧。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)步驟 9：去除狀態(tài) q2： “連接” 弧與 “*” 弧。與 M 等價(jià)的正則表達(dá)式：幾點(diǎn)說(shuō)明： 1、“去狀態(tài)”順序不同時(shí)，得到的正則表達(dá)式形式可能不一樣，但它們等價(jià)2、“去狀態(tài)” 和 “去并行弧” 操作沒(méi)有絕對(duì)的先后順序規(guī)定；但一般來(lái)說(shuō)，應(yīng)優(yōu)先執(zhí)行“去并行弧”操作，可使得后續(xù)狀態(tài)圖處理比較簡(jiǎn)單。3、當(dāng) DFA 是終止?fàn)顟B(tài)不可達(dá)時(shí)，狀態(tài)圖將不存在從始態(tài)到終態(tài)的路徑，按照算法操作，最終，會(huì)去掉標(biāo)記為 X 和 Y 狀態(tài)以外所有的狀

26、態(tài)和弧，此時(shí)，相應(yīng)的正則表達(dá)式為 。 4、上述算法不會(huì)去掉 X、Y 狀態(tài)；故判定算法可結(jié)束；可軟件實(shí)現(xiàn)算法。正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)習(xí)題：p.153, 1. 寫(xiě)出下列語(yǔ)言的表達(dá)式正則表達(dá)式的定義及性質(zhì)第四章 正則表達(dá)式正則表達(dá)式的引入正則表達(dá)式的定義及性質(zhì)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與正則文法等價(jià)正則語(yǔ)言等價(jià)描述模型總結(jié)1、將正則文法 RG 的產(chǎn)生式： A1 x1A1 | x2A2 | . | xk Ak， 其中，Ai V, xi T*改寫(xiě)為正則表達(dá)式方程式： A1 = x1A1 + x2A2 + . + xkAk 2、將 RG 中所有產(chǎn)生式聯(lián)立為正則表達(dá)式方程組。例如， RG ：S

27、 1S | 0A | RE：S = 1S + 0A + A 0S | 1A A = 0S + 1A 3、求解方程組，亦即，求解各語(yǔ)法變?cè)Z(yǔ)法范疇覆蓋字符串集合對(duì)應(yīng)的正則表達(dá)式；其中，初始符 S 的解即是代表文法 G 派生語(yǔ)言的正則表達(dá)式。正則表達(dá)式與正則文法等價(jià)RG 與 RE 等價(jià)的方程組求解算法: 定理：設(shè)有正則表達(dá)方程式 x = x + ，其中， , 為已知正則表達(dá)式，x 是未知正則表達(dá)式，那么 x = * 是方程式的一個(gè)解。正則表達(dá)式與正則文法等價(jià)證 * 是 x = x + 的一個(gè)解。將 x = * 代入方程式兩邊有：* =思路：暫將變?cè)?xi 視為已知量，其它變量 xj ( j i )

28、 視為未知量，利用定理結(jié)論求解未知量所在的方程式。例如，求解已知量 x2 式： x2 = 0 x1+1x2 = 1* 0 x1。2、將方程式 x2 的解代入未知量 x1 方程式，并利用定理結(jié)論求解。 x1 式：x1 = 1x1 + 01*0 x1 + = (1 + 01*0) x1 + = (1 + 01*0)* = (1 + 01*0)* 結(jié)果： x1 = (1 + 01*0)* x2 = 1*0 (1 + 01*0)* 求解正則表達(dá)式方程組：設(shè)方程組： x1 = 1x1 + 0 x2 + x2 = 0 x1 + 1x2 正則表達(dá)式與正則文法等價(jià)例：給定 DFA 如圖所示，求與之等價(jià)的正則表

29、達(dá)式。解：1、根據(jù)定理 3-3，寫(xiě)出等價(jià)的右線性文法： q00q1 | 1q0 q10q0 | 1q2 | 1 q20q1 | 1q02、求得相應(yīng)的正則表達(dá)式方程組： q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)2、解方程組，求代表初始狀態(tài) q0 字符串存儲(chǔ)功能的正則表達(dá)式的解3、解方程組： 由于 q2 = q0，將其代入 q1 式： q1 = 0q0 + 1q2 + 1 = ( 0 + 1 )q0 + 1 將 q1 值代入 q0 式：q0 = 0 ( ( 0 + 1 )q0 + 1) + 1q0 = 0 ( 0 + 1

30、 )q0 + 01 + 1q0 = ( 00 + 01 + 1 )q0 + 01由定理結(jié)論解得正則表達(dá)式: q0 = ( 00 + 01 + 1 )* 01故 DFA M 對(duì)應(yīng)正則表達(dá)式： L（M）= ( 00 + 01 + 1 )* 01正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0作業(yè)：1、求解下列正則表達(dá)式方程組， 即，求 x, y, z 對(duì)應(yīng)的正則表達(dá)式。2、給出接受下列語(yǔ)言的右線性文法：正則表達(dá)式與正則文法等價(jià)x = ax + byy = by + zz = x + az1）a*2) ( a + b ) ( a

31、+ b + 0 + 1 )正則表達(dá)式的引入正則表達(dá)式的定義及性質(zhì)正則表達(dá)式與有限自動(dòng)機(jī)等價(jià)正則表達(dá)式與正則文法等價(jià)正則語(yǔ)言等價(jià)描述模型總結(jié)第四章 正則表達(dá)式正則語(yǔ)言的 5 種等價(jià)描述模型：正則語(yǔ)言等價(jià)描述模型總結(jié)正則文法 （ RG ）； 確定的有窮狀態(tài)自動(dòng)機(jī)（ DFA ）；不確定的有窮狀態(tài)自動(dòng)機(jī)（ NFA ）；帶空移動(dòng)的有窮狀態(tài)自動(dòng)機(jī)（- NFA ）；正則表達(dá)式（ RE ）。五種等價(jià)描述模型及其相互模擬（定義）關(guān)系：正則語(yǔ)言等價(jià)描述模型總結(jié)正則語(yǔ)言等價(jià)模型總結(jié)1、DFA RG （用自動(dòng)機(jī)定義正則文法）： 給定 M = （Q, , , q0, F ），構(gòu)造文法 G = ( Q, , P, q0

32、)； 1）運(yùn)用 M 的狀態(tài)轉(zhuǎn)移模擬 G 推導(dǎo)過(guò)程 。 P = q a p |( q, a ) = p q a |( q, a ) = p F ； 2）M 始態(tài) q0 對(duì)應(yīng) G 起始符 S；( q, a ) = p F 定義 G 推導(dǎo)結(jié)束正則語(yǔ)言等價(jià)模型總結(jié)2、 RG NFA（正則文法定義自動(dòng)機(jī)）： 給定文法 G = ( V, T, P, S )，構(gòu)造 M = ( V Z , T, , S, Z ) 1）由 G 的推導(dǎo)過(guò)程定義 M 的狀態(tài)轉(zhuǎn)移。 B | A a B P Z 如果 A a P ( A, a ) = B | A a B P 如果 A a P 2）G 的起始符 S 對(duì)應(yīng) M 的起始狀態(tài)

33、 q0； 3）新增加狀態(tài) Z = F 為 M 的終止?fàn)顟B(tài)。正則語(yǔ)言等價(jià)模型總結(jié)1）新增加 Z 為 FA M 開(kāi)始狀態(tài)； 2）產(chǎn)生式 A a，M 有 A =(Z, a) ；3）產(chǎn)生式 A Ba，M 有 A =( B, a )； 4）規(guī)定 G 的開(kāi)始符 S 為 M 的終止?fàn)顟B(tài)。 2、 RG NFA（左線性文法定義 自動(dòng)機(jī)）： 給定文法 G = ( V, T, P, S )，構(gòu)造 M = ( V Z , T, , Z, S ) 用 G 的推導(dǎo)過(guò)程定義 M 的狀態(tài)轉(zhuǎn)移。正則語(yǔ)言等價(jià)模型總結(jié)3、 DFA RE (自動(dòng)機(jī)定義表達(dá)式） 1）圖解法 - 預(yù)處理： 去掉 DFA M 中所有不可達(dá)狀態(tài)；在 M 的

34、始態(tài) q0 和終態(tài) f1 兩端分別添加由標(biāo)記狀態(tài) X, Y。 2）去“并行”弧規(guī)則：用 r1 + r2 + + rn 標(biāo)記狀態(tài) q 到 p 之間 r1, r2, , rn 個(gè)并行?。?正則語(yǔ)言等價(jià)模型總結(jié)4）求解結(jié)果：當(dāng) X，Y 之間存在唯一一條弧時(shí)，弧上的標(biāo)記則為所求的正則表達(dá)式；如果圖中只剩下三個(gè)狀態(tài) X、Y、Z，且 X 與 Y 間不存在路徑時(shí)，刪去除 X，Y 以外的第三個(gè)狀態(tài) Z 及相關(guān)弧，所求表達(dá)式為。3、 DFA RE （圖解法） 3）去“連接”、“*” 狀態(tài)規(guī)則 ：- 用標(biāo)記為 r1r2 的弧代替狀態(tài) q 到 p、p 到 t 之間標(biāo)記分別為 r1, r2 連接弧- 用標(biāo)記為 r1r

35、3*r2 的弧代替狀態(tài) q 到 p、p 到 t 間標(biāo)記分別為r1, r2 ，并且 p 到 p 有標(biāo)記為 r3 的連接?。徽齽t語(yǔ)言等價(jià)模型總結(jié)4、 RE - NFA （正則表達(dá)式定義自動(dòng)機(jī)） 按照 RE 的遞歸定義以及定理 4 - 1 構(gòu)造性證明過(guò)程求解- NFA ： （1） r =： r = ： r = a： （2）由 r = r1 + r2 逐步構(gòu)造等價(jià)的-NFA。 由 r = r1 r2 逐步構(gòu)造等價(jià)的-NFA。 由 r = r1* 逐步構(gòu)造等價(jià)的-NFA。正則語(yǔ)言等價(jià)模型總結(jié)1、( q0, ) = q01, q02 2、( q, a ) = 1 ( q, a ) 3、( q, a ) = 2 ( q, a ) 4、( f1, ) = qf ；5、 ( f2,