8形式語(yǔ)言與自動(dòng)機(jī)-2015-第08講-正則語(yǔ)言的性質(zhì)

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

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

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

4、化描述：正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理 對(duì)任意整數(shù)對(duì)任意整數(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; 對(duì)于任意整數(shù)對(duì)于任意整數(shù) i 0，有：有： z = uviw L ; 由于由于 k j N，u, v 應(yīng)滿足條件：應(yīng)滿足條件： | u v | N, | v |1； z 仍然仍然是正則是正則語(yǔ)言語(yǔ)言 RL 的的句子句子。RL 特征的形式化描述：特征的形式化描

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

6、 uvw L，在給定正在給定正整數(shù)整數(shù) N 和某個(gè)和某個(gè) i 的條件下，可證得句子的條件下，可證得句子z = u v i w 不符合語(yǔ)言不符合語(yǔ)言 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)于 “ 對(duì)于任意整數(shù)對(duì)于任意整數(shù) i 0，u v i w RL L”的描述條件，與假設(shè)的描述條件，與假設(shè)矛盾，矛盾，故故證得證得 L 不是不是 RL。正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理例例1：證明語(yǔ)言：證明語(yǔ)言 L = 0n | n 為素?cái)?shù)為素?cái)?shù) 不是不是 R

7、L。證明：假設(shè)證明：假設(shè) L = 0n | n 為素?cái)?shù)為素?cái)?shù) 是是 RL，其滿足泵引理。設(shè)依賴于，其滿足泵引理。設(shè)依賴于 L（M） 的正整數(shù)為的正整數(shù)為 N，L 中字符串中字符串 z = 0N+p，其中，其中，N + p 是素?cái)?shù)。是素?cái)?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 ) 不不總總是素?cái)?shù)。是素?cái)?shù)。所以，當(dāng)所以，當(dāng) i = N + p + 1時(shí)，有字符串時(shí)，有字符串 z = uvN + p + 1w = 0( N + p )( 1 + k ) L，其，其與泵引理第四條矛盾，所以，與泵引理第四條矛盾，所以，L 不是不是 RL。 正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理例例2

9、：證明語(yǔ)言：證明語(yǔ)言 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 時(shí)，有時(shí)，有 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 正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理正則語(yǔ)言的泵引理1、泵引理給出關(guān)于、泵引理給出關(guān)于 RL 性質(zhì)的條件是必要條件：若性質(zhì)的條件是必要條件：若 L 是是 RL，其一定滿足泵引理給出的其一定滿足泵引理給出的 4 個(gè)條件。因

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

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

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

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

15、串 x *，有，有 ( q0, x ) = f F ( q0, x ) = f Q - F 即，即， x L（M） x L（M） 亦即，亦即， L（M） = * - L（M）。）。正則語(yǔ)言運(yùn)算的封閉性正則語(yǔ)言運(yùn)算的封閉性設(shè)設(shè) L（ r）= L（Mr），構(gòu)造與），構(gòu)造與 r 等價(jià)的等價(jià)的 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)。正則語(yǔ)言運(yùn)算

16、的封閉性正則語(yǔ)言運(yùn)算的封閉性例例3：設(shè)表達(dá)式：設(shè)表達(dá)式 r = 00 *11* 等價(jià)等價(jià) FA Mr 如圖所示，求與如圖所示，求與 r 等等價(jià)的價(jià)的 FA Mr 。q101110,100q1q2q3qtq101110,100p1p2p3p4正則語(yǔ)言運(yùn)算的封閉性正則語(yǔ)言運(yùn)算的封閉性定理定理5-3：正則語(yǔ)言正則語(yǔ)言 RL RL 在在“交交” ” 運(yùn)算下是封閉的。運(yùn)算下是封閉的。證明：證明：由由 De Morgan 定理：定理：r1r2 = ( r1 r2 ) 和和 定理定理 5-1、5-2 可證可證正則語(yǔ)言運(yùn)算的封閉性正則語(yǔ)言運(yùn)算的封閉性給定給定 r1, r2 等價(jià)的等價(jià)的 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)造分析：分析：正則語(yǔ)言運(yùn)算的封閉性正則語(yǔ)言運(yùn)算的封閉性設(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 ，對(duì)應(yīng)有序偶為，對(duì)應(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；對(duì)；對(duì) a ，q i Q1，q j Q2， 定義：定義： ( q i, q j , a ) = 1 ( q i, a ), 2 ( q j, a ) ；3、如果對(duì)于輸入字符、如果對(duì)于輸入字符 a，M1 和和 M2 中某一狀態(tài)沒有轉(zhuǎn)移狀態(tài)，則中某一狀態(tài)沒有轉(zhuǎn)移狀態(tài)，則 M 對(duì)應(yīng)的有序偶轉(zhuǎn)向陷阱態(tài)對(duì)應(yīng)的有序偶轉(zhuǎn)向陷阱態(tài) qt；正則語(yǔ)言運(yùn)算的封閉性正則語(yǔ)言運(yùn)算的封閉性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 等價(jià)的等價(jià)的 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)* 等價(jià)的等價(jià)的 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 等價(jià)的等價(jià)的 FA M1 和和 M2 ：p3p1p201r

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

21、求解算法與求解實(shí)例自動(dòng)機(jī)極小化求解算法與求解實(shí)例給定正則語(yǔ)言給定正則語(yǔ)言 L，描述，描述 L 的正則文法的正則文法 RG 和有窮自動(dòng)機(jī)和有窮自動(dòng)機(jī) FA 的描述的描述本質(zhì)相同：本質(zhì)相同：給定正則語(yǔ)言給定正則語(yǔ)言 L，正則文法正則文法 G 或或 自動(dòng)機(jī)自動(dòng)機(jī) DFA 均根據(jù)語(yǔ)言均根據(jù)語(yǔ)言的結(jié)構(gòu)特征，的結(jié)構(gòu)特征，對(duì)對(duì) L 字母表的克林閉包字母表的克林閉包 * 中字符串進(jìn)行中字符串進(jìn)行等價(jià)劃分（分類等價(jià)劃分（分類 )，以求字符串的各個(gè)等價(jià)類，以求字符串的各個(gè)等價(jià)類 。 切入點(diǎn)：切入點(diǎn)：自動(dòng)機(jī)極小化思路自動(dòng)機(jī)極小化思路例：例：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 個(gè)集合兩兩互不相交；個(gè)集合兩兩互不相交；5 個(gè)集合的并構(gòu)成個(gè)集合的并構(gòu)成 M 識(shí)別輸入字母表識(shí)別輸入字母表 0，1 的的克林閉包；克林閉包；5 個(gè)集合是關(guān)于個(gè)集合是關(guān)于 0,

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

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

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

26、x ) = ( q0, y ) = q。1、 DFA M 對(duì)對(duì) * 的等價(jià)劃分的等價(jià)劃分綜合綜合定義定義 5-4 和和 定義定義 3-4，有：，有： x RM y q Q, x, y set ( q )最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念例例6：設(shè)：設(shè) L = 0*10* 對(duì)應(yīng)的對(duì)應(yīng)的 DFA M 如圖所示。如圖所示。滿足關(guān)系滿足關(guān)系 RM 各狀態(tài)各狀態(tài) q 中所存字符串的等價(jià)描述：中所存字符串的等價(jià)描述：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 其它至少含兩個(gè)其它至少含兩個(gè) 1 的的 x, y 串串定義定義5-5：設(shè)設(shè) L *，對(duì)于，對(duì)于 x, y *，由，由 L 確定的確定的 *上的關(guān)系上的關(guān)系 RL 定定義為：義為： x RL y 對(duì)于對(duì)于 z *，x z L y z L 。注：如果注：如果 x RL y，則在，則在 x, y 后連接后連接

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

29、 M = ，M 確定的確定的 * 上的關(guān)上的關(guān)系系 RM 為右不變等價(jià)關(guān)系。為右不變等價(jià)關(guān)系。3、 * 上的上的右右不變等價(jià)關(guān)系不變等價(jià)關(guān)系最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念證明：證明：1、RM 是等價(jià)關(guān)系是等價(jià)關(guān)系： x, y ， 自反性：自反性： x RM x |=| ( q0, x ) =( q0, x ) ； 對(duì)稱性：對(duì)稱性： 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 ) 由等號(hào)由等號(hào) = 的傳遞性：的傳遞性： ( 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； 故對(duì)故對(duì) z ， 有有 ( q0, x z ) = ( ( q0, x ) , z ) = ( q, z ) = ( ( q0, y ), z ) = ( q0, y z ) 最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念定理定理 5-4：對(duì)于任意對(duì)于任意 L * ，L 所確定的所確定的 *

31、上的關(guān)系上的關(guān)系 RL 為右不變等價(jià)為右不變等價(jià)關(guān)系。關(guān)系。（ 顯然顯然 ）3、 * 上的上的右右不變等價(jià)關(guān)系不變等價(jià)關(guān)系最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念最簡(jiǎn)自動(dòng)機(jī)求解的相關(guān)概念滿足等價(jià)關(guān)系滿足等價(jià)關(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、滿足等價(jià)關(guān)系、滿足等價(jià)關(guān)系 RL(M) 的字符串不一定滿足等價(jià)類的字符串不一定滿足等價(jià)類 RM 。例如，。例如， 由于由于 x = 00 set ( q0 ), y = 0 set ( q1 ), 因此，因此， 00 RM 0 不成立；不成立；RM 和和 RL（M）確定等價(jià)類的聯(lián)系與區(qū)別：確定等價(jià)類的聯(lián)系與區(qū)別：DFA M 接受語(yǔ)言接受語(yǔ)言 L( M ) = 0*10*然而，若設(shè)然而，若設(shè) z = 10， 由于由于 0010 L( M ) 010 L( M ) ，因此，因此，x, y 滿足語(yǔ)言滿足語(yǔ)言 L( M ) = 0*10*

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

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

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

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

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

38、是 上一個(gè)右不變等價(jià)關(guān)系，它把上一個(gè)右不變等價(jià)關(guān)系，它把 L 劃分成有限個(gè)等價(jià)類的劃分成有限個(gè)等價(jià)類的并集。注意到并集。注意到 RL 也是也是一個(gè)右不變等價(jià)關(guān)系，對(duì)于一個(gè)右不變等價(jià)關(guān)系，對(duì)于 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 個(gè)等價(jià)類，則個(gè)等價(jià)類，則 RL 把把 * 劃分成劃分成 不多于不多于 K 個(gè)等價(jià)類。個(gè)等價(jià)類。 Myhill Nerode （邁希爾（邁希爾-尼羅德）定理尼羅德）定理證明證明 3） 1）：）：L 確定的等價(jià)關(guān)系確定的等價(jià)關(guān)系 R

39、L 具有有窮指數(shù)具有有窮指數(shù) |* / RL|，可將，可將 L 劃分劃分成有限個(gè)等價(jià)類成有限個(gè)等價(jià)類 L是正則語(yǔ)言，可被一個(gè)是正則語(yǔ)言，可被一個(gè) DFA 接受。接受。設(shè)設(shè) L * ，構(gòu)造識(shí)別語(yǔ)言，構(gòu)造識(shí)別語(yǔ)言 L 的的 DFA M = （Q, , q0, F ）如下：）如下：令令* 上上右不變等價(jià)關(guān)系右不變等價(jià)關(guān)系 RL 的商集（等價(jià)類的集合）為的商集（等價(jià)類的集合）為 DFA M 的狀態(tài)集，即，的狀態(tài)集，即， Q = * / RL = x | x *, y ： y x y RL x = set( q ) 令令 DFA 的初始狀態(tài)和終止?fàn)顟B(tài)集：的初始狀態(tài)和終止?fàn)顟B(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 將將* 劃分劃分為有限為有限等價(jià)類算法：等價(jià)類算法： 給定接受正則語(yǔ)言給定接受正則語(yǔ)言 L 的的 DFA M ，用右不變等價(jià)關(guān)系，用右不變等價(jià)關(guān)系 RM 將將 * 劃分為有限個(gè)劃分為有限個(gè) 等價(jià)類，通過合并等價(jià)類，通過合并 set( qi ) ，求得語(yǔ)言，求得語(yǔ)言 L 確定確定 RL 劃分劃分 * 的有限等價(jià)類集合。的有限等價(jià)類集合。Myhil

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

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

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

44、 ( q4 ), 任意任意 z * ， z 不含 1 時(shí)，1 z L( M )， 10 z L( M ) z 含 1 時(shí)， 1 z L( M )，01 z L( M )， 所以，所以， 1 z L( M ) 10 z L( M ), set(q2), set(q4) 可合并。可合并。5、取取 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 接受語(yǔ)言：接受語(yǔ)言：

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*； 含一個(gè)含一個(gè) 1 的串：的串： 1 = set ( q2 ) set ( q3 ) set ( q4 ) = 0*10*含多個(gè)含多個(gè) 1 的串：的串： 11 = set ( q5 ) = 0* 1 0* 1( 0 + 1 )*最小最小 DFA M：結(jié)果：等價(jià)關(guān)系結(jié)果：等價(jià)關(guān)系 RL(

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

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

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

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