8形式語言與自動機-2015-第08講-正則語言的性質(zhì)

1、形式語言與自動機形式語言與自動機Formal Languages and Automata Theory教師教師：胡：胡春明、趙永望春明、趙永望第五章第五章 正則語言的性質(zhì)正則語言的性質(zhì) http:/ 正則語言的性質(zhì)正則語言的性質(zhì)正則語言的泵引理正則語言的泵引理正則語言運算的封閉性正則語言運算的封閉性自動機的極小化自動機的極小化正則語言的判定算法正則語言的判定算法*分析分析：1 1、識別、識別 RL RL 句子的句子的 DFA DFA 僅有有限個狀態(tài)。僅有有限個狀態(tài)。2 2、用、用 DFA M DFA M 接受無窮語言接受無窮語言 L L，L L 中一定存在一個足夠長的句中一定存在一個足夠長的

2、句子，使得子，使得 DFA DFA 在識別該句子時，需要重復(fù)地經(jīng)過某些狀態(tài)。在識別該句子時，需要重復(fù)地經(jīng)過某些狀態(tài)。DFA處理句子經(jīng)歷處理句子經(jīng)歷的狀態(tài)序列的狀態(tài)序列DFA處理句子經(jīng)歷處理句子經(jīng)歷的重復(fù)狀態(tài)序列的重復(fù)狀態(tài)序列正則語言的泵引理正則語言的泵引理正則語言的泵引理正則語言的泵引理1、假設(shè)、假設(shè) L 是是 RL，DFA M = ， 滿足滿足 L( M ) = L， M 具有有限個狀態(tài)，即，具有有限個狀態(tài)，即，| Q | = N，且，且 Q 中狀態(tài)均為可達狀態(tài)。中狀態(tài)均為可達狀態(tài)。2、取、取 L 中任意句子中任意句子 z = a1a2am ( m N )，并有，并有 qm F。3、由于、由

3、于 m N ，讀字符的狀態(tài)序列，讀字符的狀態(tài)序列 q0, q1, , qN 中至少有兩個狀態(tài)相同。中至少有兩個狀態(tài)相同。假設(shè)狀態(tài)假設(shè)狀態(tài) qk = qj, 對于對于 k j N，有，有，( q0, a1a2ak ) = qk; ( qk, ak+1 ak+2aj ) = qj = qk; ( qj, aj+1aj+2am ) = qm 對于任意整數(shù)對于任意整數(shù) i 0，可能有，可能有 ( qk, (ak+1ak+2aj )i ) =( q k, (ak+1ak+2aj )i-1 ) . =( qk, (ak+1ak+2aj ) = qk = qj 泵操作泵操作RL 特征的形式化描述：特征的形式

4、化描述：正則語言的泵引理正則語言的泵引理 對任意整數(shù)對任意整數(shù) i 0, ( q0, a1a2ak( ak+1ak+2aj )iaj+1aj+2am ) = qmF亦有：亦有： a1a2ak(ak+1ak+2aj )iaj+1aj+2am L（M）設(shè)設(shè) u = a1a2ak, v = ak+1ak+2aj, w = aj+1aj+2am; 對于任意整數(shù)對于任意整數(shù) i 0，有：有： z = uviw L ; 由于由于 k j N，u, v 應(yīng)滿足條件：應(yīng)滿足條件： | u v | N, | v |1； z 仍然仍然是正則是正則語言語言 RL 的的句子句子。RL 特征的形式化描述：特征的形式化描

5、述：正則語言的泵引理正則語言的泵引理 定義定義5-1：泵引理：泵引理設(shè)設(shè) L 為為 RL，存在僅依賴于語言，存在僅依賴于語言 L 的某個正整數(shù)的某個正整數(shù) N，對于，對于 z L， 如果如果 | z | N，則存在，則存在 u, v, w，滿足以下條件：，滿足以下條件：1、z = uvw ;2、| uv | N; 3、| v | 1;4、對于任意整數(shù)對于任意整數(shù) i 0，u v i w L。正則語言的泵引理正則語言的泵引理 泵引理應(yīng)用：用反證法泵引理應(yīng)用：用反證法證明給定語言證明給定語言 L 不是不是 RL。假設(shè)假設(shè) L 是是 RL，L 應(yīng)滿足泵引理。構(gòu)造某句子應(yīng)滿足泵引理。構(gòu)造某句子 z =

6、 uvw L，在給定正在給定正整數(shù)整數(shù) N 和某個和某個 i 的條件下，可證得句子的條件下，可證得句子z = u v i w 不符合語言不符合語言 L 中句中句子的結(jié)構(gòu)特征子的結(jié)構(gòu)特征，即有即有句子句子 z = u v i w 不不屬于屬于 RL L。由于由于 L 中存在句子中存在句子 z 的結(jié)構(gòu)不滿足泵引理的結(jié)構(gòu)不滿足泵引理 RL 關(guān)于關(guān)于 “ 對于任意整數(shù)對于任意整數(shù) i 0，u v i w RL L”的描述條件，與假設(shè)的描述條件，與假設(shè)矛盾，矛盾，故故證得證得 L 不是不是 RL。正則語言的泵引理正則語言的泵引理例例1：證明語言：證明語言 L = 0n | n 為素數(shù)為素數(shù) 不是不是 R

7、L。證明：假設(shè)證明：假設(shè) L = 0n | n 為素數(shù)為素數(shù) 是是 RL，其滿足泵引理。設(shè)依賴于，其滿足泵引理。設(shè)依賴于 L（M） 的正整數(shù)為的正整數(shù)為 N，L 中字符串中字符串 z = 0N+p，其中，其中，N + p 是素數(shù)。是素數(shù)。根據(jù)泵引理，必存在根據(jù)泵引理，必存在 u, v, w, 使得使得 z = uvw 且且 | v |1；這里，；這里，v 是是 0 組成的非組成的非空串，不妨設(shè)空串，不妨設(shè) v = 0k, （k1），），w = 0j，u = 0N + p k j，從而有，從而有， u vi w = 0N + p k j (0k)i 0j = 0N + p + ( i -1 )

8、k， 取取 i = N + p + 1， N + p + ( i 1 ) k = N + p + ( N + p + 1 - 1) k = ( N + p ) + ( N + p ) k = ( N + p )( 1 + k ) 由于已知由于已知 k1， 因此，因此，( N + p )( 1 + k ) 不不總總是素數(shù)。是素數(shù)。所以，當所以，當 i = N + p + 1時，有字符串時，有字符串 z = uvN + p + 1w = 0( N + p )( 1 + k ) L，其，其與泵引理第四條矛盾，所以，與泵引理第四條矛盾，所以，L 不是不是 RL。 正則語言的泵引理正則語言的泵引理例例2

9、：證明語言：證明語言 L = 0n1n | n1 不是不是 RL。證明：假設(shè)證明：假設(shè) L = 0n1n | n1 是是 RL，其應(yīng)滿足泵引理。設(shè)依賴于，其應(yīng)滿足泵引理。設(shè)依賴于 L( M ) 的的正整數(shù)為正整數(shù)為 N ，L 中有字符串為中有字符串為 z = 0N1N。根據(jù)泵引理，必存在根據(jù)泵引理，必存在 u, v, w, 構(gòu)成句子構(gòu)成句子 z = uvw，其中，其中 | uv | N，| v |1；這；這里，里，v 只能是由只能是由 0 組成的非空串。組成的非空串。不失一般性地可設(shè)，不失一般性地可設(shè)， v = 0k，（，（k 1），），w = 0j 1N， u = 0N k - j，從而有，

10、從而有， u vi w = 0N k - j (0k)i 0j 1N ，取取 i = 2 時，有時，有 u v2 w = 0N k - j (0k)2 0j 1N = 0N + k 1N由于已知由于已知 k 1， 有有 N N + k,于是有：于是有： 字符串字符串 z = 0N + k 1N L，與泵引理第四條矛盾，故，與泵引理第四條矛盾，故 L 不是不是 RL 正則語言的泵引理正則語言的泵引理正則語言的泵引理正則語言的泵引理1、泵引理給出關(guān)于、泵引理給出關(guān)于 RL 性質(zhì)的條件是必要條件：若性質(zhì)的條件是必要條件：若 L 是是 RL，其一定滿足泵引理給出的其一定滿足泵引理給出的 4 個條件。因

11、此，應(yīng)用泵引理證明一個條件。因此，應(yīng)用泵引理證明一個語言不是個語言不是 RL時，常用時，常用“反證法反證法” 。2、泵引理給出的、泵引理給出的 RL 性質(zhì)的條件性質(zhì)的條件不是充分條件不是充分條件；滿足泵引理滿足泵引理所給所給 4 個條件的語言個條件的語言不一定就是不一定就是 RL。因此，泵引理。因此，泵引理只能用于只能用于證明給定語言不是證明給定語言不是 RL；而不能證明給定語言是；而不能證明給定語言是 RL。說明：說明：正則語言的泵引理正則語言的泵引理1、給定一個、給定一個L，如何證明它不是，如何證明它不是RL。思考：思考：2、給定一個、給定一個L，如何證明它是，如何證明它是RL。正則語言的

12、泵引理正則語言的泵引理正則語言運算的封閉性正則語言運算的封閉性自動機的極小自動機的極小化化正則語言的判定算法正則語言的判定算法*第五章第五章 正則語言的性質(zhì)正則語言的性質(zhì)定義定義5-2：如果對某類語言進行某種運算后，所得的結(jié)果仍為該類語言的如果對某類語言進行某種運算后，所得的結(jié)果仍為該類語言的句子，則稱該類語言對此運算是封閉的，或稱該類語言對運算句子，則稱該類語言對此運算是封閉的，或稱該類語言對運算具有封閉性。具有封閉性。正則語言運算的封閉性正則語言運算的封閉性定義定義5-3：稱某語言類對某運算滿足有效封閉性，是指給定該類語言中任稱某語言類對某運算滿足有效封閉性，是指給定該類語言中任意兩個語言

13、意兩個語言 L1、L2 的形式化表示，對二語言進行運算后所得的形式化表示，對二語言進行運算后所得語言仍然具有形式化表示算法。語言仍然具有形式化表示算法。正則語言運算的封閉性正則語言運算的封閉性定理定理5-1：正則語言正則語言 RL RL 對對“并并”、“乘積乘積”和和“閉包閉包”運算封閉。運算封閉。定理定理5-2：正則語言正則語言 RL RL 對對“補補”運算封閉。運算封閉。定理定理5-3：正則語言正則語言 RL RL 對對“交交”運算封閉。運算封閉。正則語言運算的封閉性正則語言運算的封閉性定義定義4-1：設(shè)字母表為設(shè)字母表為 ，正則表達式遞歸定義如下：，正則表達式遞歸定義如下：正則語言運算的

14、封閉性正則語言運算的封閉性定理定理5-1：正則語言對正則語言對“并并”、“乘積乘積”和和“閉包閉包”運算封閉。運算封閉。正則語言運算的封閉性正則語言運算的封閉性對于對于 r = r1*，構(gòu)造相應(yīng)，構(gòu)造相應(yīng)-NFA對于對于 r = r1r2，構(gòu)造相應(yīng)，構(gòu)造相應(yīng)-NFA對于對于 r = r1 + r2，構(gòu)造相應(yīng)，構(gòu)造相應(yīng)-NFA定理定理5-25-2： 正則語言正則語言 RL RL 在在“補補” ” 運算下是封閉的。運算下是封閉的。證明：證明：設(shè)設(shè) L 是是 上的上的 RL，則存在，則存在 DFA M = ，滿足，滿足 L（M）= L。取。取 DFA M = ，顯然，對于任意字符串顯然，對于任意字符

15、串 x *，有，有 ( q0, x ) = f F ( q0, x ) = f Q - F 即，即， x L（M） x L（M） 亦即，亦即， L（M） = * - L（M）。）。正則語言運算的封閉性正則語言運算的封閉性設(shè)設(shè) L（ r）= L（Mr），構(gòu)造與），構(gòu)造與 r 等價的等價的 FA Mr 算法：算法：Mr 的始態(tài)作為的始態(tài)作為 Mr 的始態(tài)；的始態(tài)； Mr 與與 Mr 的狀態(tài)轉(zhuǎn)移函數(shù)不變；的狀態(tài)轉(zhuǎn)移函數(shù)不變；將將 Mr 所有非終態(tài)所有非終態(tài) ( 包括陷阱態(tài)包括陷阱態(tài) qt ) 作為作為 Mr 的終態(tài)；的終態(tài)；將將 Mr 所有終態(tài)作為所有終態(tài)作為 Mr 的非終態(tài)。的非終態(tài)。正則語言運算

16、的封閉性正則語言運算的封閉性例例3：設(shè)表達式：設(shè)表達式 r = 00 *11* 等價等價 FA Mr 如圖所示，求與如圖所示，求與 r 等等價的價的 FA Mr 。q101110,100q1q2q3qtq101110,100p1p2p3p4正則語言運算的封閉性正則語言運算的封閉性定理定理5-3：正則語言正則語言 RL RL 在在“交交” ” 運算下是封閉的。運算下是封閉的。證明：證明：由由 De Morgan 定理：定理：r1r2 = ( r1 r2 ) 和和 定理定理 5-1、5-2 可證可證正則語言運算的封閉性正則語言運算的封閉性給定給定 r1, r2 等價的等價的 DFA M1 = ，D

17、FA M2 = ，構(gòu)造，構(gòu)造 DFA M，使得，使得 L( M ) = L( M1 ) L( M2 )。L( r1r2 ) 的的 DFA M 構(gòu)造構(gòu)造分析：分析：正則語言運算的封閉性正則語言運算的封閉性設(shè)設(shè) L( M1 ) = L( r1 )、L( M2 ) = L( r2 ) ，構(gòu)造接受，構(gòu)造接受 L( r1r2 ) 的的 DFA M = 算法：算法：4、若、若 M1，M2 中含有中含有陷阱態(tài)陷阱態(tài) qt ，對應(yīng)有序偶為，對應(yīng)有序偶為 M 的陷阱態(tài)的陷阱態(tài) qt。 2、 M 的始態(tài)為的始態(tài)為 M1 和和 M2 始態(tài)有序偶；始態(tài)有序偶； M 的終態(tài)為的終態(tài)為 M1和和 M2 的終態(tài)的終態(tài)有序偶

18、；有序偶； 1、取、取 = 1 2 ；Q = Q1Q2；對；對 a ，q i Q1，q j Q2， 定義：定義： ( q i, q j , a ) = 1 ( q i, a ), 2 ( q j, a ) ；3、如果對于輸入字符、如果對于輸入字符 a，M1 和和 M2 中某一狀態(tài)沒有轉(zhuǎn)移狀態(tài)，則中某一狀態(tài)沒有轉(zhuǎn)移狀態(tài)，則 M 對應(yīng)的有序偶轉(zhuǎn)向陷阱態(tài)對應(yīng)的有序偶轉(zhuǎn)向陷阱態(tài) qt；正則語言運算的封閉性正則語言運算的封閉性2、根據(jù)、根據(jù) NFA 求求 DFA M 算法：算法： q1, q3 為始態(tài)；為始態(tài)； q2, q3 為終態(tài)。為終態(tài)。2、 M 的狀態(tài)表。的狀態(tài)表。 例例4：設(shè)：設(shè) r1= 01*

19、 ，r2=(01)* ；求；求 r = r1r2 等價的等價的 DFA M。q3q401q2q110M1M23、 令令 DFA M 狀態(tài)：狀態(tài)： p1= q1, q3 -始態(tài)始態(tài), p2 = q2, q4 p3 = q2, q3 -終態(tài)，終態(tài)，與與 r = 01*( 01)* 等價的等價的 DFA M：狀態(tài)狀態(tài)說明說明狀態(tài)列狀態(tài)列輸入字符列輸入字符列01始態(tài)始態(tài) q1, q3 q2, q4 qt, qt q2, q4 qt, qt q2, q3 終態(tài)終態(tài) q2, q3 qt, q4 q2, qt 解：解：1、與、與 r1 和和 r2 等價的等價的 FA M1 和和 M2 ：p3p1p201r

20、= 01*( 01)* = 01正則代換（正則代換（Substitution）：）：正則語言運算的封閉性正則語言運算的封閉性同態(tài)映射（同態(tài)映射（Homomorphism）：）：商（商（quotient）：）：29正則語言的泵引理正則語言的泵引理正則語言運算的封閉性正則語言運算的封閉性自動機的極小自動機的極小化化正則語言的判定算法正則語言的判定算法*第五章第五章 正則語言性質(zhì)正則語言性質(zhì)自動機的極小化自動機的極小化問題的引出及問題的引出及 DFA 極小化思路極小化思路最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念Myhill Nerode （米希爾（米希爾-尼羅德）定理尼羅德）定理自動機極小化

21、求解算法與求解實例自動機極小化求解算法與求解實例給定正則語言給定正則語言 L，描述，描述 L 的正則文法的正則文法 RG 和有窮自動機和有窮自動機 FA 的描述的描述本質(zhì)相同：本質(zhì)相同：給定正則語言給定正則語言 L，正則文法正則文法 G 或或 自動機自動機 DFA 均根據(jù)語言均根據(jù)語言的結(jié)構(gòu)特征，的結(jié)構(gòu)特征，對對 L 字母表的克林閉包字母表的克林閉包 * 中字符串進行中字符串進行等價劃分（分類等價劃分（分類 )，以求字符串的各個等價類，以求字符串的各個等價類 。 切入點：切入點：自動機極小化思路自動機極小化思路例：例：L = x000 | x 0,1* x001 | x 0,1 * set (

22、q0) = x | x *, x = 或者或者 x 以以 1 結(jié)尾但不以結(jié)尾但不以 001 結(jié)尾結(jié)尾 ;set (q1) = x | x *, x = 0 或者或者 x 以以 10 結(jié)尾結(jié)尾 set (q2) = x | x *, x = 00 或者或者 x 以以 100 結(jié)尾結(jié)尾 set (q3) = x | x *, x 以以 000 結(jié)尾結(jié)尾 set (q4) = x | x *, x 以以 001 結(jié)尾結(jié)尾 5 個集合兩兩互不相交；個集合兩兩互不相交；5 個集合的并構(gòu)成個集合的并構(gòu)成 M 識別輸入字母表識別輸入字母表 0，1 的的克林閉包；克林閉包；5 個集合是關(guān)于個集合是關(guān)于 0,

23、1 * 的一個等價劃分。的一個等價劃分。自動機極小化思路自動機極小化思路可知：可知：1）DFA M 的的每個可達狀態(tài)存儲一個輸入字符子串的等價類，記為每個可達狀態(tài)存儲一個輸入字符子串的等價類，記為 set ( q )自動機極小化思路自動機極小化思路3） DFA M 的極小化：求解將的極小化：求解將* 劃分形成的等價類個數(shù)最少，劃分形成的等價類個數(shù)最少，亦即，用于存儲亦即，用于存儲字符子串字符子串的狀態(tài)數(shù)最少的自動機。的狀態(tài)數(shù)最少的自動機。2）對于）對于同一正則語言同一正則語言 L，不同結(jié)構(gòu)的自動機模型對不同結(jié)構(gòu)的自動機模型對 * 進行的進行的等價等價劃分不同，所得到字符子串的等價類也不盡相同劃

24、分不同，所得到字符子串的等價類也不盡相同 。自動機極小化思路自動機極小化思路例：對于例：對于 正則語言正則語言 L = 0*10*，兩種，兩種不同結(jié)構(gòu)不同結(jié)構(gòu) DFA 如圖所示。如圖所示。自動機的極小化自動機的極小化問題的引出及極小化思路問題的引出及極小化思路最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念Myhill Nerode （米希爾（米希爾-尼羅德）定理尼羅德）定理自動機極小化求解算法與求解實例自動機極小化求解算法與求解實例最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念1、 DFA M 對對 * 的等價劃分的等價劃分2、 語言語言 L 對對 * 的等價劃分的等價劃分3、 * 上上右

25、不變等價關(guān)系右不變等價關(guān)系4、 * 上的等價指數(shù)上的等價指數(shù)1、 DFA M 對對 * 的等價劃分的等價劃分回顧定義回顧定義 3-4 ：設(shè)設(shè) DFA M = ，對于，對于 q Q，定義引導(dǎo)，定義引導(dǎo) M 從開始狀態(tài)到達狀態(tài)從開始狀態(tài)到達狀態(tài) q 對應(yīng)的輸入字符串集合為：對應(yīng)的輸入字符串集合為：set ( q ) = x | x *, ( q0, x ) = q 最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念定義定義 5-4：設(shè)設(shè) DFA M = ，M 確定的確定的 * 上的關(guān)系上的關(guān)系 RM 定定義為：義為： 對于對于 x, y *，滿足以下等式：，滿足以下等式： x RM y ( q0,

26、x ) = ( q0, y ) = q。1、 DFA M 對對 * 的等價劃分的等價劃分綜合綜合定義定義 5-4 和和 定義定義 3-4，有：，有： x RM y q Q, x, y set ( q )最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念例例6：設(shè)：設(shè) L = 0*10* 對應(yīng)的對應(yīng)的 DFA M 如圖所示。如圖所示。滿足關(guān)系滿足關(guān)系 RM 各狀態(tài)各狀態(tài) q 中所存字符串的等價描述：中所存字符串的等價描述：q0： ( 00 )n RM ( 00 )m n, m 0 q1： 0( 00 )n RM 0( 00 )m n, m 0 q2：

27、 ( 00 )n1 RM ( 00 )m1 n, m 0 q3： 0( 00 )n1 RM 0( 00 )m1 n, m 0 q4： 0(00 )n10k RM 0(00 )m10h n, m 0; k, h 1 0n10k RM 0m10h n, m 0; k, h 1q5： x RM y 其它至少含兩個其它至少含兩個 1 的的 x, y 串串定義定義5-5：設(shè)設(shè) L *，對于，對于 x, y *，由，由 L 確定的確定的 *上的關(guān)系上的關(guān)系 RL 定定義為：義為： x RL y 對于對于 z *，x z L y z L 。注：如果注：如果 x RL y，則在，則在 x, y 后連接后連接

28、* 中的任何字符串中的任何字符串 z, x z 和和 y z 要么同是要么同是 L 的句子；要么都不是的句子；要么都不是 L 的句子。的句子。2、 語言語言 L 對對 * 的等價劃分的等價劃分最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念定義定義5-6：設(shè)設(shè) R 是是*上的等價關(guān)系，對于上的等價關(guān)系，對于 x, y *，如果，如果 x R y，對，對于于 z * ，必有，必有 x z R y z 成立，則稱成立，則稱 R 是是右不變等價關(guān)右不變等價關(guān)系。系。3、 * 上的上的右右不變等價關(guān)系不變等價關(guān)系最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念定理定理 5-3：對于任意對于任意 DFA

29、 M = ，M 確定的確定的 * 上的關(guān)上的關(guān)系系 RM 為右不變等價關(guān)系。為右不變等價關(guān)系。3、 * 上的上的右右不變等價關(guān)系不變等價關(guān)系最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念證明：證明：1、RM 是等價關(guān)系是等價關(guān)系： x, y ， 自反性：自反性： x RM x |=| ( q0, x ) =( q0, x ) ； 對稱性：對稱性： x RM y |=| ( q0, x ) =( q0, y ) |=| ( q0, y ) =( q0, x ) = y RM x 傳遞性：傳遞性： 設(shè)設(shè) x RM y |=| ( q0, x ) =( q0, y )； y RM z |=| (

30、q0, y ) =( q0, z ) 由等號由等號 = 的傳遞性：的傳遞性： ( q0, x ) = ( q0, z ) 由由RM的定義有：的定義有： x RM z 2、RM 是右不變關(guān)系是右不變關(guān)系： 設(shè)設(shè) x RM y，由，由 RM 定義有：定義有：( q0, x ) =( q0, y ) = q； 故對故對 z ， 有有 ( q0, x z ) = ( ( q0, x ) , z ) = ( q, z ) = ( ( q0, y ), z ) = ( q0, y z ) 最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念定理定理 5-4：對于任意對于任意 L * ，L 所確定的所確定的 *

31、上的關(guān)系上的關(guān)系 RL 為右不變等價為右不變等價關(guān)系。關(guān)系。（ 顯然顯然 ）3、 * 上的上的右右不變等價關(guān)系不變等價關(guān)系最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念滿足等價關(guān)系滿足等價關(guān)系 RM 的的 x, y, 一定滿足一定滿足 x RL(M) y：1、x, y set ( q )，有，有( q0, x ) =( q0, y ) = q， z *, ( q0, xz ) =( q0, x ), z ) =( q, z ) = ( ( q0, y ) , z ) = ( q0, yz ) ( q0, x z ) F ( q0, y z ) F 或者或者 x z L(M ) y z L(M

32、 ) 所以，所以， x R L( M ) y 成立。成立。2、滿足等價關(guān)系、滿足等價關(guān)系 RL(M) 的字符串不一定滿足等價類的字符串不一定滿足等價類 RM 。例如，。例如， 由于由于 x = 00 set ( q0 ), y = 0 set ( q1 ), 因此，因此， 00 RM 0 不成立；不成立；RM 和和 RL（M）確定等價類的聯(lián)系與區(qū)別：確定等價類的聯(lián)系與區(qū)別：DFA M 接受語言接受語言 L( M ) = 0*10*然而，若設(shè)然而，若設(shè) z = 10， 由于由于 0010 L( M ) 010 L( M ) ，因此，因此，x, y 滿足語言滿足語言 L( M ) = 0*10*

33、確定的關(guān)系確定的關(guān)系 R L（ M ）： 00 R L( M ) 0 成立成立 對于任意對于任意 DFA M = ，有：，有：1）一般來說，如果一般來說，如果 x RM y，一定有，一定有 x RL（M） y ；反之，不一定成立。；反之，不一定成立。亦即，亦即，按照按照 RM 分類，分在同一等價類中的字符串分類，分在同一等價類中的字符串 x, y，按照，按照 RL(M) 分類分類時，一定會分在同一等價類中；被時，一定會分在同一等價類中；被 RM 分在不同等價類中的字符串分在不同等價類中的字符串 x, y，按照按照 RL(M) 分類時，也可能被分在分類時，也可能被分在 RL(M) 的同一等價類中

34、。的同一等價類中。結(jié)論結(jié)論：2） 由于由于 RM 對對 * 的劃分比的劃分比 RL(M) 對對 * 的劃分更細，的劃分更細， RM 的多個等的多個等價類可對應(yīng)到價類可對應(yīng)到 RL( M ) 的一個等價類，因此，稱的一個等價類，因此，稱 RM 是對是對 RL( M ) 的加細的加細最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念設(shè)設(shè) R 是是 * 上的等價關(guān)系，將上的等價關(guān)系，將 | * / R | 定義為定義為 R 關(guān)于關(guān)于* 的指數(shù)，簡的指數(shù)，簡稱為稱為 R 的指數(shù)。以下關(guān)系成立：的指數(shù)。以下關(guān)系成立： | * / RL(M) | | * /

35、RM | | * / RL(M) | | * / RM | |Q|。4、 * 上的上的 R 指數(shù)指數(shù)問題的引出及極小化思路問題的引出及極小化思路最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理自動機極小化求解算法與求解實例自動機極小化求解算法與求解實例自動機的極小化自動機的極小化定理定理 5-5：以下三個命題等價以下三個命題等價 ： 1） L *是正則語言是正則語言 RL。 2） L 是是 * 上上某個右不變等價關(guān)系某個右不變等價關(guān)系 RM 的有限個等價類的并集。的有限個等價類的并集。 3） L 確定的等價關(guān)系確定的等價關(guān)系

36、 RL 具有有窮指數(shù)具有有窮指數(shù) |* / RL|。()qFsetqMyhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理證明證明 1） 2）：）： L *是正則語言是正則語言 L 是是 * 上某個右不變等上某個右不變等價關(guān)系價關(guān)系 RM 的有限個等價類的并集。的有限個等價類的并集。 由于由于RM 可把可把 L（M）中的字符串劃分成最多）中的字符串劃分成最多 | Q | 個等價類；并且，個等價類；并且，F(xiàn) Q，故故 L（M）是不多于）是不多于 | Q | 個等價類的并集。個等價類的并集。由由 DFA M = 定義定義右不變等價關(guān)系右不變等價關(guān)系 RM （已證），滿足（已證），滿

37、足 對于對于 x, y ， x RM y 當且僅當當且僅當 ( q0, x ) = ( q0, y ) 并且并且 對于對于 z ，若，若 x RM y，有，有( q0, xz ) = ( ( q0, x ) , z ) = ( ( q0, y ), z ) = ( q0, yz ) Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理證明證明 2） 3）：是）：是 * 上某個具有有窮指數(shù)的右不變等價關(guān)系上某個具有有窮指數(shù)的右不變等價關(guān)系 RM 等等價類的并集價類的并集 L 確定的等價關(guān)系確定的等價關(guān)系 RL 具有有窮指數(shù)具有有窮指數(shù) |* / RL |。設(shè)設(shè) RM 是不是是不

38、是 上一個右不變等價關(guān)系，它把上一個右不變等價關(guān)系，它把 L 劃分成有限個等價類的劃分成有限個等價類的并集。注意到并集。注意到 RL 也是也是一個右不變等價關(guān)系，對于一個右不變等價關(guān)系，對于 x, y, z 有有 x RM y xz RM yz x z L y z L x RL y 表明表明 x RM y x RL y；故如若；故如若 RM 把把 * 劃分成劃分成 K 個等價類，則個等價類，則 RL 把把 * 劃分成劃分成 不多于不多于 K 個等價類。個等價類。 Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理證明證明 3） 1）：）：L 確定的等價關(guān)系確定的等價關(guān)系 R

39、L 具有有窮指數(shù)具有有窮指數(shù) |* / RL|，可將，可將 L 劃分劃分成有限個等價類成有限個等價類 L是正則語言，可被一個是正則語言，可被一個 DFA 接受。接受。設(shè)設(shè) L * ，構(gòu)造識別語言，構(gòu)造識別語言 L 的的 DFA M = （Q, , q0, F ）如下：）如下：令令* 上上右不變等價關(guān)系右不變等價關(guān)系 RL 的商集（等價類的集合）為的商集（等價類的集合）為 DFA M 的狀態(tài)集，即，的狀態(tài)集，即， Q = * / RL = x | x *, y ： y x y RL x = set( q ) 令令 DFA 的初始狀態(tài)和終止狀態(tài)集：的初始狀態(tài)和終止狀態(tài)集：q0 = ；F = x |

40、 x L 令令 DFA 的狀態(tài)轉(zhuǎn)移函數(shù)：的狀態(tài)轉(zhuǎn)移函數(shù)：( x , a ) = xa ；其中，其中， x Q， a 如此構(gòu)造的如此構(gòu)造的 M 是接受是接受 L 的的 DFA。Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理1）RL 將將* 劃分劃分為有限為有限等價類算法：等價類算法： 給定接受正則語言給定接受正則語言 L 的的 DFA M ，用右不變等價關(guān)系，用右不變等價關(guān)系 RM 將將 * 劃分為有限個劃分為有限個 等價類，通過合并等價類，通過合并 set( qi ) ，求得語言，求得語言 L 確定確定 RL 劃分劃分 * 的有限等價類集合。的有限等價類集合。Myhil

41、l Nerode 定理的應(yīng)用：定理的應(yīng)用：2）證明一個語言）證明一個語言 L 不是不是 RL：RL 可將可將 * 劃分為無窮個等價劃分為無窮個等價類。類。Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理Myhill Nerode 定理定理例例8：對對 */RM = set (q0), set (q1), set (q2), set (q3), set (q4), set (q5) 中元素兩兩進中元素兩兩進行考察，通過合并行考察，通過合并 RM 等價類獲得等價類獲得 RL( M ) 的等價類集合，從而，求得最小自動機的等價類集合，從而，求得最小自動機。1、取取 00set

42、( q0 ), 000 set ( q1 ), 任意任意 z * ， z 含且僅含一個 1 時， 00z L( M )， 000z L( M ) z 不含1或含多個1 時，00z L( M )，000z L( M )， 所以所以, 00 z L( M )，000 z L( M ), set( q0 ) 與與 set( q1 )可合并為可合并為 RL( M ) 同一等價類同一等價類2、取取00set ( q0 ), 001set ( q2 ), 取取 z = 1* 有：00z L(M)， 001z L(M)。 所以所以, set( q0 ) 與與 set( q2 )不可合并為不可合并為 RL(M

43、) 同一等價類同一等價類同理，同理， set( q0 ) 與 set( q3 )， set( q4 )， set( q5 ) 的等價類都不可合并。設(shè)設(shè) DFA M 接受語言：接受語言： L = 0*10*3、取取 001 set ( q2 ), 01 set ( q3 ), 任意任意 z * ， z 不含 1 時， 001 z L(M)， 01 z L(M) z 含 1 時， 001 z L( M )，01 z L( M )， 所以，所以， 001z L( M ) 01z L( M ), set( q2 ), set( q3 ) 可合并?？珊喜ⅰ?、取取 1set ( q2 ), 10 set

44、 ( q4 ), 任意任意 z * ， z 不含 1 時，1 z L( M )， 10 z L( M ) z 含 1 時， 1 z L( M )，01 z L( M )， 所以，所以， 1 z L( M ) 10 z L( M ), set(q2), set(q4) 可合并?？珊喜ⅰ?、取取 1 set ( q2 ), 11 set ( q5 ), 設(shè) z =, 有 1 z = 1 = 1，11 z = 11 = 11； 則有, 1 z L( M )； 11 z L( M )，所以，所以，set( q2 ) 與與 set( q5 ) 不可合并。不可合并。設(shè)設(shè) DFA M 接受語言：接受語言：

45、L = 0*10*Myhill Nerode 定理定理*/ RL( M ) = set ( q0 ) set ( q1 ), set ( q2 ) set ( q3 ) set ( q4 ), set ( q5 ) 其中，其中， 不含不含 1 的串：的串： 0 = set (q0) set (q1) = 0*； 含一個含一個 1 的串：的串： 1 = set ( q2 ) set ( q3 ) set ( q4 ) = 0*10*含多個含多個 1 的串：的串： 11 = set ( q5 ) = 0* 1 0* 1( 0 + 1 )*最小最小 DFA M：結(jié)果：等價關(guān)系結(jié)果：等價關(guān)系 RL(

46、M ) 劃分劃分 * 的字符串等價類：的字符串等價類：Myhill Nerode 定理定理推論推論 5-1： 對于任意的對于任意的 RL L，在同構(gòu)意義下，接受，在同構(gòu)意義下，接受 L 的極小的極小化化 DFA 是唯一的。是唯一的。Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理58自動機的極小化自動機的極小化問題的引出及極小化思路問題的引出及極小化思路最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理自動機極小化求解算法與求解實例自動機極小化求解算法與求解實例方法方法1：嚴格按照由嚴格按照由 RL 劃分

47、劃分 求求等價類的定義，從等價類的定義，從 set ( q ) 和和 set ( p ) 中各取一適當?shù)淖址懈魅∫贿m當?shù)淖址?x, y，利用右不變性質(zhì)考察：對于任意，利用右不變性質(zhì)考察：對于任意字符串字符串 z，x z 和和 y z 是否同時屬于是否同時屬于 L 和同時不屬于和同時不屬于 L。（如前例）。（如前例）評價：評價：1、需要對、需要對 M 中任意狀態(tài)中任意狀態(tài) p、q 兩兩配對考察；兩兩配對考察；2、計算量與、計算量與M 中包含狀態(tài)的個數(shù)中包含狀態(tài)的個數(shù) | Q | 以及所選字符串以及所選字符串 x, y, z 的長度的長度 有關(guān)，需要分析有關(guān)，需要分析 x, y, z 的結(jié)構(gòu)

48、特征。的結(jié)構(gòu)特征。存在兩種合并方案：存在兩種合并方案：自動機極小化求解算法自動機極小化求解算法算法的時間復(fù)雜度較高。算法的時間復(fù)雜度較高。方法方法2：1、不考慮哪些狀態(tài)可以合并，反之，考慮哪些狀態(tài)不能合并。、不考慮哪些狀態(tài)可以合并，反之，考慮哪些狀態(tài)不能合并。 - 找出所有不可合并狀態(tài)，剩下的就是可合并狀態(tài)；找出所有不可合并狀態(tài)，剩下的就是可合并狀態(tài)；自動機極小化求解算法自動機極小化求解算法存在兩種合并方案：存在兩種合并方案：2、考察從終態(tài)往始態(tài)方向進行搜索，確定任意兩狀態(tài)是否為不可合、考察從終態(tài)往始態(tài)方向進行搜索，確定任意兩狀態(tài)是否為不可合并狀態(tài)。并狀態(tài)。定義定義 57：設(shè)設(shè) DFA M =

49、 ， 如果如果 x , 使得使得 Q 中的中的兩個狀態(tài)兩個狀態(tài) q 和和 p，( q, x ) F 和和( p, x ) F 中有且僅有一中有且僅有一個成立，則稱個成立，則稱 q 和和 p 是可區(qū)分的，否則是可區(qū)分的，否則 q 和和 p 等價，記作等價，記作 q p。自動機極小化求解算法自動機極小化求解算法可區(qū)分可區(qū)分 |=| 不可合并不可合并 。命題：命題：設(shè)狀態(tài)設(shè)狀態(tài) p 和和 q 不能合并，對于其它待尚未考察狀態(tài)不能合并，對于其它待尚未考察狀態(tài) p 和和 q，若存在字符，若存在字符 a，使得，使得 ( q, a ) = q, ( p, a ) = p，則可，則可斷定狀態(tài)斷定狀態(tài) p 和和 q 也不能合并。也不能合并。自動機極小化算法：自動機極小化算法：輸入：輸入： 給定的給定的 DFA M = ；1）