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

1、形式語言與自動機Formal Languages and Automata Theory第五章 正則語言的性質(zhì)幾種語言模型之間的關(guān)系：簡單回顧上節(jié)課的內(nèi)容：RGDFARENFA圖解法分別構(gòu)造自動機添加終止態(tài)Z對AaB|a特殊處理每一個中間狀態(tài)都是非終結(jié)符問題：是否能夠構(gòu)造一個有窮自動機，識別語言：看一個例子：Sq0q1q201有什么辦法幫助我們更容易的判別一個語言是否是正則語言？第五章 正則語言的性質(zhì)正則語言的泵引理正則語言運算的封閉性自動機的極小化正則語言的判定算法*分析：1、識別 RL 句子的 DFA 僅有有限個狀態(tài)。2、用 DFA M 接受無窮語言 L，L 中一定存在一個足夠長的句子，使

2、得 DFA 在識別該句子時，需要重復地經(jīng)過某些狀態(tài)。DFA處理句子經(jīng)歷的狀態(tài)序列DFA處理句子經(jīng)歷的重復狀態(tài)序列正則語言的泵引理正則語言的泵引理1、假設(shè) L 是 RL，DFA M = ， 滿足 L( M ) = L， M 具有有限個狀態(tài)，即，| Q | = N，且 Q 中狀態(tài)均為可達狀態(tài)。2、取 L 中任意句子 z = a1a2am ( m N )，并有 qm F。3、由于 m N ，讀字符的狀態(tài)序列 q0, q1, , qN 中至少有兩個狀態(tài)相同。假設(shè)狀態(tài) qk = qj, 對于 k j N，有，( q0, a1a2ak ) = qk; ( qk, ak+1 ak+2aj ) = qj =

3、qk; ( qj, aj+1aj+2am ) = qm 對于任意整數(shù) i 0，可能有 ( qk, (ak+1ak+2aj )i ) =( q k, (ak+1ak+2aj )i-1 ) . =( qk, (ak+1ak+2aj ) = qk = qj 泵操作RL 特征的形式化描述：正則語言的泵引理 對任意整數(shù) i 0, ( q0, a1a2ak( ak+1ak+2aj )iaj+1aj+2am ) = qmF亦有： a1a2ak(ak+1ak+2aj )iaj+1aj+2am L（M）設(shè) u = a1a2ak, v = ak+1ak+2aj, w = aj+1aj+2am; 對于任意整數(shù) i

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

5、正整數(shù) N 和某個 i 的條件下，可證得句子z = u v i w 不符合語言 L 中句子的結(jié)構(gòu)特征，即有句子 z = u v i w 不屬于 RL L。由于 L 中存在句子 z 的結(jié)構(gòu)不滿足泵引理 RL 關(guān)于 “ 對于任意整數(shù) i 0，u v i w RL L”的描述條件，與假設(shè)矛盾，故證得 L 不是 RL。正則語言的泵引理例1：證明語言 L = 0n | n 為素數(shù) 不是 RL。證明：假設(shè) L = 0n | n 為素數(shù) 是 RL，其滿足泵引理。設(shè)依賴于 L（M） 的正整數(shù)為 N，L 中字符串 z = 0N+p，其中，N + p 是素數(shù)。根據(jù)泵引理，必存在 u, v, w, 使得 z = u

6、vw 且 | v |1；這里，v 是 0 組成的非空串，不妨設(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 ) 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ù)。所以，當 i = N + p + 1時，有字符串 z =

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

8、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)于 RL 性質(zhì)的條件是必要條件：若 L 是 RL，其一定滿足泵引理給出的 4 個條件。因此，應用泵引理證明一個語言不是 RL時，常用“反證法” 。2、泵引理給出的 RL 性質(zhì)的條件不是充分條件；滿足泵引理所給 4 個條件的語言不一定就是 RL。因此，泵引理只能用于證明給定

9、語言不是 RL；而不能證明給定語言是 RL。說明：正則語言的泵引理1、給定一個L，如何證明它不是RL。思考：2、給定一個L，如何證明它是RL。正則語言的泵引理正則語言運算的封閉性自動機的極小化正則語言的判定算法*第五章 正則語言的性質(zhì)定義5-2：如果對某類語言進行某種運算后，所得的結(jié)果仍為該類語言的句子，則稱該類語言對此運算是封閉的，或稱該類語言對運算具有封閉性。正則語言運算的封閉性定義5-3：稱某語言類對某運算滿足有效封閉性，是指給定該類語言中任意兩個語言 L1、L2 的形式化表示，對二語言進行運算后所得語言仍然具有形式化表示算法。正則語言運算的封閉性定理5-1：正則語言 RL 對“并”、“

10、乘積”和“閉包”運算封閉。定理5-2：正則語言 RL 對“補”運算封閉。定理5-3：正則語言 RL 對“交”運算封閉。正則語言運算的封閉性定義4-1：設(shè)字母表為 ，正則表達式遞歸定義如下：正則語言運算的封閉性定理5-1：正則語言對“并”、“乘積”和“閉包”運算封閉。正則語言運算的封閉性對于 r = r1*，構(gòu)造相應-NFA對于 r = r1r2，構(gòu)造相應-NFA對于 r = r1 + r2，構(gòu)造相應-NFA定理5-2： 正則語言 RL 在“補” 運算下是封閉的。證明：設(shè) L 是 上的 RL，則存在 DFA M = ，滿足 L（M）= L。取 DFA M = ，顯然，對于任意字符串 x *，有

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

12、p3p4正則語言運算的封閉性定理5-3：正則語言 RL 在“交” 運算下是封閉的。證明：由 De Morgan 定理：r1r2 = ( r1 r2 ) 和 定理 5-1、5-2 可證正則語言運算的封閉性給定 r1, r2 等價的 DFA M1 = ，DFA M2 = ，構(gòu)造 DFA M，使得 L( M ) = L( M1 ) L( M2 )。L( r1r2 ) 的 DFA M 構(gòu)造分析：正則語言運算的封閉性設(shè) L( M1 ) = L( r1 )、L( M2 ) = L( r2 ) ，構(gòu)造接受 L( r1r2 ) 的 DFA M = 算法：4、若 M1，M2 中含有陷阱態(tài) qt ，對應有序偶為

13、M 的陷阱態(tài) qt。 2、 M 的始態(tài)為 M1 和 M2 始態(tài)有序偶； M 的終態(tài)為 M1和 M2 的終態(tài)有序偶； 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)，則 M 對應的有序偶轉(zhuǎn)向陷阱態(tài) qt；正則語言運算的封閉性2、根據(jù) NFA 求 DFA M 算法： q1, q3 為始態(tài)； q2, q3 為終態(tài)。2、 M 的狀態(tài)表。 例4：設(shè) r1= 01* ，r2=(01)* ；求 r = r1r2

14、 等價的 DFA M。q3q401q2q110M1M23、 令 DFA M 狀態(tài)： p1= q1, q3 -始態(tài), p2 = q2, q4 p3 = q2, q3 -終態(tài)，與 r = 01*( 01)* 等價的 DFA M：狀態(tài)說明狀態(tài)列輸入字符列01始態(tài) q1, q3 q2, q4 qt, qt q2, q4 qt, qt q2, q3 終態(tài) q2, q3 qt, q4 q2, qt 解：1、與 r1 和 r2 等價的 FA M1 和 M2 ：p3p1p201r = 01*( 01)* = 01正則代換（Substitution）：正則語言運算的封閉性同態(tài)映射（Homomorphism）：商

15、（quotient）：29正則語言的泵引理正則語言運算的封閉性自動機的極小化正則語言的判定算法*第五章 正則語言性質(zhì)自動機的極小化問題的引出及 DFA 極小化思路最簡自動機求解的相關(guān)概念Myhill Nerode （米希爾-尼羅德）定理自動機極小化求解算法與求解實例給定正則語言 L，描述 L 的正則文法 RG 和有窮自動機 FA 的描述本質(zhì)相同：給定正則語言 L，正則文法 G 或 自動機 DFA 均根據(jù)語言的結(jié)構(gòu)特征，對 L 字母表的克林閉包 * 中字符串進行等價劃分（分類 )，以求字符串的各個等價類 。 切入點：自動機極小化思路例：L = x000 | x 0,1* x001 | x 0,1

16、 * set (q0) = x | x *, x = 或者 x 以 1 結(jié)尾但不以 001 結(jié)尾 ;set (q1) = x | x *, x = 0 或者 x 以 10 結(jié)尾 set (q2) = x | x *, x = 00 或者 x 以 100 結(jié)尾 set (q3) = x | x *, x 以 000 結(jié)尾 set (q4) = x | x *, x 以 001 結(jié)尾 5 個集合兩兩互不相交；5 個集合的并構(gòu)成 M 識別輸入字母表 0，1 的克林閉包；5 個集合是關(guān)于 0, 1 * 的一個等價劃分。自動機極小化思路可知：1）DFA M 的每個可達狀態(tài)存儲一個輸入字符子串的等價類，記

17、為 set ( q )自動機極小化思路3） DFA M 的極小化：求解將* 劃分形成的等價類個數(shù)最少，亦即，用于存儲字符子串的狀態(tài)數(shù)最少的自動機。2）對于同一正則語言 L，不同結(jié)構(gòu)的自動機模型對 * 進行的等價劃分不同，所得到字符子串的等價類也不盡相同 。自動機極小化思路例：對于 正則語言 L = 0*10*，兩種不同結(jié)構(gòu) DFA 如圖所示。自動機的極小化問題的引出及極小化思路最簡自動機求解的相關(guān)概念Myhill Nerode （米希爾-尼羅德）定理自動機極小化求解算法與求解實例最簡自動機求解的相關(guān)概念1、 DFA M 對 * 的等價劃分2、 語言 L 對 * 的等價劃分3、 * 上右不變等價

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

19、相關(guān)概念最簡自動機求解的相關(guān)概念例6：設(shè) L = 0*10* 對應的 DFA M 如圖所示。滿足關(guān)系 RM 各狀態(tài) q 中所存字符串的等價描述：q0： ( 00 )n RM ( 00 )m n, m 0 q1： 0( 00 )n RM 0( 00 )m n, m 0 q2： ( 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

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

21、 * 上的關(guān)系 RM 為右不變等價關(guān)系。3、 * 上的右不變等價關(guān)系最簡自動機求解的相關(guān)概念證明：1、RM 是等價關(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è) x RM y |=| ( q0, x ) =( q0, y )； y RM z |=| ( q0, y ) =( q0, z ) 由等號 = 的傳遞性： ( q0, x ) = ( q0, z ) 由RM的定義有： x RM z

22、2、RM 是右不變關(guān)系： 設(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)概念定理 5-4：對于任意 L * ，L 所確定的 *上的關(guān)系 RL 為右不變等價關(guān)系。（ 顯然 ）3、 * 上的右不變等價關(guān)系最簡自動機求解的相關(guān)概念滿足等價關(guān)系 RM 的 x, y, 一定滿足 x RL(M) y：1、x, y set ( q )，有( q0, x ) =( q0, y )

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

24、10， 由于 0010 L( M ) 010 L( M ) ，因此，x, y 滿足語言 L( M ) = 0*10* 確定的關(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) 的同一等價類中。結(jié)論：2） 由于 RM 對 * 的劃分比 RL(M) 對 * 的劃分更細， R

25、M 的多個等價類可對應到 RL( M ) 的一個等價類，因此，稱 RM 是對 RL( M ) 的加細最簡自動機求解的相關(guān)概念最簡自動機求解的相關(guān)概念設(shè) R 是 * 上的等價關(guān)系，將 | * / R | 定義為 R 關(guān)于* 的指數(shù)，簡稱為 R 的指數(shù)。以下關(guān)系成立： | * / RL(M) | | * / RM | | * / RL(M) | | * / RM | |Q|。4、 * 上的 R 指數(shù)問題的引出及極小化思路最簡自動機求解的相關(guān)概念Myhill Nerode （邁希爾-尼羅德）定理自動機極小化求解算法與求解實例自動機的極小化定理 5-5：以下三個命題等價 ： 1） L *是正則語言 R

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

27、RM y，有( q0, xz ) = ( ( q0, x ) , z ) = ( ( q0, y ), z ) = ( q0, yz ) Myhill Nerode （邁希爾-尼羅德）定理證明 2） 3）：是 * 上某個具有有窮指數(shù)的右不變等價關(guān)系 RM 等價類的并集 L 確定的等價關(guān)系 RL 具有有窮指數(shù) |* / RL |。設(shè) RM 是不是 上一個右不變等價關(guān)系，它把 L 劃分成有限個等價類的并集。注意到 RL 也是一個右不變等價關(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 把 * 劃分

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

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

30、 = set (q0), set (q1), set (q2), set (q3), set (q4), set (q5) 中元素兩兩進行考察，通過合并 RM 等價類獲得 RL( M ) 的等價類集合，從而，求得最小自動機。1、取 00set ( 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

31、、取00set ( q0 ), 001set ( q2 ), 取 z = 1* 有：00z L(M)， 001z L(M)。 所以, set( q0 ) 與 set( q2 )不可合并為 RL(M) 同一等價類同理， set( q0 ) 與 set( q3 )， set( q4 )， set( q5 ) 的等價類都不可合并。設(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 )， 所以，

32、 001z L( M ) 01z L( M ), set( q2 ), set( q3 ) 可合并。4、取 1set ( q2 ), 10 set ( 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) 可合并。5、取 1 set ( q2 ), 11 set ( q5 ), 設(shè) z =, 有 1 z = 1 = 1，11 z = 11 = 11； 則有, 1 z L( M )； 11 z L(

33、M )，所以，set( q2 ) 與 set( q5 ) 不可合并。設(shè) DFA M 接受語言： 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 )*最小 D

34、FA M：結(jié)果：等價關(guān)系 RL( M ) 劃分 * 的字符串等價類：Myhill Nerode 定理推論 5-1： 對于任意的 RL L，在同構(gòu)意義下，接受 L 的極小化 DFA 是唯一的。Myhill Nerode （邁希爾-尼羅德）定理58自動機的極小化問題的引出及極小化思路最簡自動機求解的相關(guān)概念Myhill Nerode （邁希爾-尼羅德）定理自動機極小化求解算法與求解實例方法1：嚴格按照由 RL 劃分 求等價類的定義，從 set ( q ) 和 set ( p ) 中各取一適當?shù)淖址?x, y，利用右不變性質(zhì)考察：對于任意字符串 z，x z 和 y z 是否同時屬于 L 和同時不屬

35、于 L。（如前例）評價：1、需要對 M 中任意狀態(tài) p、q 兩兩配對考察；2、計算量與M 中包含狀態(tài)的個數(shù) | Q | 以及所選字符串 x, y, z 的長度 有關(guān)，需要分析 x, y, z 的結(jié)構(gòu)特征。存在兩種合并方案：自動機極小化求解算法算法的時間復雜度較高。方法2：1、不考慮哪些狀態(tài)可以合并，反之，考慮哪些狀態(tài)不能合并。 - 找出所有不可合并狀態(tài)，剩下的就是可合并狀態(tài)；自動機極小化求解算法存在兩種合并方案：2、考察從終態(tài)往始態(tài)方向進行搜索，確定任意兩狀態(tài)是否為不可合并狀態(tài)。定義 57：設(shè) DFA M = ， 如果 x , 使得 Q 中的兩個狀態(tài) q 和 p，( q, x ) F 和( p, x ) F 中有且僅有一個成立，則稱 q 和 p 是可區(qū)分的，否則 q 和 p 等價，記作 q p。自動機極小化求解算法可區(qū)分 |=| 不可合并 。命題：設(shè)狀態(tài) p 和 q 不能合并，對于其它待尚未考察狀態(tài) p 和 q，若存在字符 a，使得 ( q, a ) = q, ( p, a ) = p，則可斷定狀態(tài) p 和 q 也不能合并。自動機極小化算法：輸入： 給定的 DFA M = ；1） 對每個 p F，q Q F 的狀態(tài)對 ( q, p ) 加上可區(qū)分標記； /* 標記 p 和 q 不可合并2） 對每個狀態(tài)對 ( q, p ) F F