形式語言與自動機：第05講-正則表達式與正則語言

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

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

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

4、），記作 r = s。正則表達式的定義及性質(zhì)例：設(shè) = 0，1 ，上正則表達式以及其表示的語言如下：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 )正則表達式表示的正則語言：正則表達式的定義及性質(zhì)例：設(shè) = 0，1 ，上正則表達式以及其表示的語言如下：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 ) =正則表達式表示的正則語言：正則表達式的定義及性質(zhì) 00 。 x | x 是至少含兩個連續(xù) 0 的串 x | x 是倒數(shù)第十個字符為 1 的串 x | x 是 011 結(jié)尾的串 。 0n 1m 2k | n, m, k1 。 0n 1m 2k | n, m, k0 。習(xí)題：p.153, 2. 理解正則表達式正則表達式的定義及性質(zhì)習(xí)題：p.153, 1. 寫出下列語言的表達式正則表達式的定義及性質(zhì)可以證明，字母表 上正則表達式

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

7、R*正則表達式的定義及性質(zhì)由歸納原理可知，對任意整數(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為表達式 r、s 對應(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正則表達式的定義及性質(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 ） 的正則表達式為 ( r*s* ) *； 集

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

10、表 上任意正則表達式 r，構(gòu)造相應(yīng)的 FA M，使得 L（r）= L（M）； 1、歸納證明：施歸納于正則表達式運算符 (+、連接、*) 的個數(shù) 2、構(gòu)造 FA M 的終止?fàn)顟B(tài)。 基礎(chǔ)： 設(shè)正則表達式運算符的個數(shù) n = 0，構(gòu)造 FA 存在以下三種情況： r =：有 - NFA 滿足要求。 r = ：有 - NFA 滿足要求。 r = a：有 - NFA 滿足要求。 結(jié)論對 n = 0 成立。正則表達式與有限自動機等價1、對于 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）對 q Q1 - f1 ，a ：( q, a ) = 1 ( q, a ) ； 對 q Q2 - f2 ，a ：( q, a ) = 2 ( q, a ) ； 3） ( f1, ) = f ； ( f2, ) = f 由于1( f1, ) = 2( f2, ) = 歸納：設(shè)結(jié)論對運算符個數(shù)為 n k ( k0 )的表達式成立，證當(dāng) n = k + 1 時，結(jié)論仍然成立。添加運算符時, 存在 r1 + r2, r1r2, r* 三種情況。正則表達式與有限自動機等價1、構(gòu)造與表達式 r = r1

12、 + r2 等價的-NFA 的圖示：正則表達式與有限自動機等價正則表達式與有限自動機等價1、對于 r = r1 + r2，求證：L（r1 + r2）= L（M）。由歸納假設(shè)： L（r1）= L（M1）， L（r2）= L（M2）； 由正則表達式性質(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 ) 時，有 x L（ M ）。正則表達式與有限自動機等價設(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 等價 ” 證畢 ）正則表達式與有限自動機等價例4：

14、給定正則表達式 r1 = 01* ，r2 = ( 01 )*，以及與其等價的 FA M1、M2 如下，構(gòu)造與表達式 r = r1 + r2 等價的- NFA Mq02q2201q12q0110M1M21q0q12q02q2201q010qf解：正則表達式與有限自動機等價2、對于 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）對 q Q1 - f1 ，a ，( q, a ) = 1 ( q, a ) ； 2）對 q Q2， a ，( q, a ) = 2 (

15、 q, a ) ； 3）( f1, ) = q02 ； 設(shè) ( f1, ) = ( f2, ) = 。歸納：設(shè)結(jié)論對運算符個數(shù)為 n k ( k0 )的表達式成立，證 n= k+ 1 時結(jié)論仍然成立。由正則表達式定義, 存在 r1 + r2, r1r2, r* 三種情況。正則表達式與有限自動機等價2、構(gòu)造與表達式 r = r1r2 等價的-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 。正則表達式與有限自動機等價2、對于 r = r1r2 ，求證：L（r1 r2）= L（M）。由歸納假設(shè)有： L ( r1 ) = L ( M1 )， L ( r2 ) = L ( M2 )；由正則表達式性質(zhì)： L ( r1 r2 ) = L ( r1 ) L ( r2 ) = L ( M1 ) L ( M2 )只需證： L（ M1 ）L（ M2 ）= L（ M ） 。 （ “”）故有，x L（M）。正則表達式與有限自動機等價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 等價 證畢。設(shè) x L（M），即有，( q01, x ) = f2 ，并且 x = x1 x2，使得，例5：設(shè) r1 = ( bc )* ，r2 = ( ba )* ；識別它們的 FA 分別為 M1 和 M2，構(gòu)造與 r = r1r2 等價的- NFA M。 q

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

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

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

21、1 = 01* ，r2 = ( 01 )*，求 r = r1 + r2 的 DFA M。 解： 1、構(gòu)造識別 r1 和 r2 的 FA M1 和 M2；正則表達式與有限自動機的等價性q02q2201q11q0110M1M21q010q0q11q02q2201qf2、構(gòu)造識別 r = r1 + r2 的 DFA M 的狀態(tài)圖與狀態(tài)表：其中，始態(tài)( q0,) = q01, q02 ；終態(tài)( q11, q02 ,) = qf 。3、畫出 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)說明等價證明與轉(zhuǎn)換算法： 給定有窮自動機 FA，利用圖解法求相應(yīng)等價的正則表達式。正則表達式與有限自動機等價定義4-4： 稱正則表達式 r 與自動機 FA 等價，如果有 L（r）= L（M）。2-1、 “圖解法”：1、預(yù)

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

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

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

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

27、 1S | 0A | RE：S = 1S + 0A + A 0S | 1A A = 0S + 1A 3、求解方程組，亦即，求解各語法變元語法范疇覆蓋字符串集合對應(yīng)的正則表達式；其中，初始符 S 的解即是代表文法 G 派生語言的正則表達式。正則表達式與正則文法等價RG 與 RE 等價的方程組求解算法: 定理：設(shè)有正則表達方程式 x = x + ，其中， , 為已知正則表達式，x 是未知正則表達式，那么 x = * 是方程式的一個解。正則表達式與正則文法等價證 * 是 x = x + 的一個解。將 x = * 代入方程式兩邊有：* =思路：暫將變元 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)* 求解正則表達式方程組：設(shè)方程組： x1 = 1x1 + 0 x2 + x2 = 0 x1 + 1x2 正則表達式與正則文法等價例：給定 DFA 如圖所示，求與之等價的正則表

29、達式。解：1、根據(jù)定理 3-3，寫出等價的右線性文法： q00q1 | 1q0 q10q0 | 1q2 | 1 q20q1 | 1q02、求得相應(yīng)的正則表達式方程組： q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0正則表達式與有限自動機等價2、解方程組，求代表初始狀態(tài) q0 字符串存儲功能的正則表達式的解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é)論解得正則表達式: q0 = ( 00 + 01 + 1 )* 01故 DFA M 對應(yīng)正則表達式： L（M）= ( 00 + 01 + 1 )* 01正則表達式與有限自動機等價q0 = 0q1 + 1q0q1 = 0q0 + 1q2 + 1q2 = 0q1 + 1q0作業(yè)：1、求解下列正則表達式方程組， 即，求 x, y, z 對應(yīng)的正則表達式。2、給出接受下列語言的右線性文法：正則表達式與正則文法等價x = ax + byy = by + zz = x + az1）a*2) ( a + b ) ( a

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

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

33、 q0； 3）新增加狀態(tài) Z = F 為 M 的終止?fàn)顟B(tài)。正則語言等價模型總結(jié)1）新增加 Z 為 FA M 開始狀態(tài)； 2）產(chǎn)生式 A a，M 有 A =(Z, a) ；3）產(chǎn)生式 A Ba，M 有 A =( B, a )； 4）規(guī)定 G 的開始符 S 為 M 的終止?fàn)顟B(tài)。 2、 RG NFA（左線性文法定義 自動機）： 給定文法 G = ( V, T, P, S )，構(gòu)造 M = ( V Z , T, , Z, S ) 用 G 的推導(dǎo)過程定義 M 的狀態(tài)轉(zhuǎn)移。正則語言等價模型總結(jié)3、 DFA RE (自動機定義表達式） 1）圖解法 - 預(yù)處理： 去掉 DFA M 中所有不可達狀態(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 個并行??； 正則語言等價模型總結(jié)4）求解結(jié)果：當(dāng) X，Y 之間存在唯一一條弧時，弧上的標(biāo)記則為所求的正則表達式；如果圖中只剩下三個狀態(tài) X、Y、Z，且 X 與 Y 間不存在路徑時，刪去除 X，Y 以外的第三個狀態(tài) Z 及相關(guān)弧，所求表達式為。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語言等價模型總結(jié)4、 RE - NFA （正則表達式定義自動機） 按照 RE 的遞歸定義以及定理 4 - 1 構(gòu)造性證明過程求解- NFA ： （1） r =： r = ： r = a： （2）由 r = r1 + r2 逐步構(gòu)造等價的-NFA。 由 r = r1 r2 逐步構(gòu)造等價的-NFA。 由 r = r1* 逐步構(gòu)造等價的-NFA。正則語言等價模型總結(jié)1、( q0, ) = q01, q02 2、( q, a ) = 1 ( q, a ) 3、( q, a ) = 2 ( q, a ) 4、( f1, ) = qf ；5、 ( f2,