05 正則語(yǔ)言的性質(zhì).ppt

1、1,形式語(yǔ)言與自動(dòng)機(jī),第5章 正則語(yǔ)言的性質(zhì),2,主要內(nèi)容,正則語(yǔ)言(RL)的性質(zhì) 泵引理及其應(yīng)用 并、乘積、閉包、補(bǔ)、交 正則代換、同態(tài)、逆同態(tài)的封閉性 從正則語(yǔ)言固有特征尋求表示的一致性 Myhill-Nerode定理 FA的極小化 正則語(yǔ)言的幾個(gè)判定問(wèn)題 空否、有窮否、兩個(gè)DFA等價(jià)否、成員關(guān)系,3,5.1 正則語(yǔ)言的泵引理,DFA在處理一個(gè)足夠長(zhǎng)的句子的過(guò)程中，必定會(huì)重復(fù)地經(jīng)過(guò)某一個(gè)狀態(tài)。 換句話說(shuō)，在 DFA 的狀態(tài)轉(zhuǎn)移圖中，必定存在一條含有回路的從啟動(dòng)狀態(tài)到某個(gè)終止?fàn)顟B(tài)的路。 由于是回路，所以 DFA 可以根據(jù)實(shí)際需要沿著這個(gè)回路循環(huán)運(yùn)行，相當(dāng)于這個(gè)回路中弧上的標(biāo)記構(gòu)成的非空子串可

2、以重復(fù)任意多次。,4,泵引理,5,泵引理,M = ( Q, , , q0 , F ) | Q |= N z = a1a2am , mN (q0 , a1a2ah) = qh 狀態(tài)序列 q0, q1, ,qN 中，至少有兩個(gè)狀態(tài)是相同：qk=qj (q0 , a1a2ak) = qk (qk , ak+1aj) = qj = qk (qj , aj+1am) = qm 因此，可設(shè) z = uvw，其中 u= a1a2ak，v=ak+1aj，w = aj+1am,6,泵引理,對(duì)于任意的整數(shù) i 0 (qk , (ak+1aj)i ) =(qk , (ak+1aj)i-1 ) =(qk , ak+1

3、aj) = qk 故(q0 , a1a2ak (ak+1aj)i aj+1am) = qm 也就是說(shuō)， a1a2ak (ak+1aj)i aj+1amL(M) 即 uviwL 。,7,泵引理 (pumping lemma),設(shè) L 為一個(gè) 正則語(yǔ)言 ，則存在僅依賴于 L 的正整數(shù) N， 對(duì)于 zL，如果 | z |N，則存在 u, v, w，滿足 (1) z = uvw； (2) | uv | N； (3) | v | 1； (4) 對(duì)于任意的整數(shù) i 0，uviw L； (5) N 不大于接受 L 的最小 DFA M 的狀態(tài)數(shù)。,我們總能夠在離 z 的開(kāi)始處不太遠(yuǎn)的地方找到一個(gè)非空的 串 v

4、，然后可以把它看作一個(gè)“泵”，重復(fù) v 任意多次， 或者去掉它，而所得到的結(jié)果串仍然屬于L。,8,例5-1,證明 0n1n | n1 不是 RL。 證明：假設(shè) L= 0n1n | n1是 RL。 不妨設(shè) N 是泵引理所指的僅依賴于 L 的正整數(shù)，取 z = 0N1N ，則 z L。 按照泵引理所述，存在 u, v, w，使得 z=uvw。 由于 | uv | N，| v | 1，所以 v 只能由0組成， 可設(shè) v=0k，k1 此時(shí)有，u = 0N-k-j , w=0j1N 從而有，uviw = 0N-k-j (0k)i 0j1N = 0N+(i-1)k1N 當(dāng) i =2 時(shí)，有： uv2w=0

5、N+(2-1)k1N = 0N+k1N 注意到 k1，所以，N+kN。 這就是說(shuō)，0N+k1NL。 這與泵引理矛盾。所以，L不是 RL。,9,例5-2,證明 0n | n 為素?cái)?shù) 不是 RL。 證明：假設(shè) L= 0n | n為素?cái)?shù) 是 RL。 取 z=0N+p L ，N+p 是素?cái)?shù)。 不妨設(shè) v=0k，k1 從而有 uviw=0N+p-k-j(0k)i0j=0N+p+(i-1)k 當(dāng) i=N+p+1時(shí)， N+p+(i-1)k = N+p+(N+p+1-1)k = N+p+(N+p)k = (N+p)(1+k) 注意到 k1，所以 N+p+(N+p+1-1)k=(N+p)(1+k) 不是素?cái)?shù)。故

6、當(dāng) i=N+p+1時(shí)， uvN+p+1w=0(N+p)(1+k) L 這與泵引理矛盾。所以，L 不是 RL。,10,例5-3,證明 0n1m2n+m | m, n1 不是 RL。 證明：假設(shè) L= 0n1m2n+m |m, n1 是 RL。 取 z=0N1N22N 設(shè) v=0kk1 從而有 uviw = 0N-k-j(0k)i0j1N22N = 0N+(i-1)k1N22N uv0w = 0N+(0-1)k1N22N = 0N-k1N22N 注意到 k1， N-k+N=2N-k2N 0N-k1N22N L 這個(gè)結(jié)論與泵引理矛盾。所以，L 不是 RL。,11,泵引理的說(shuō)明,用來(lái)證明一個(gè)語(yǔ)言不是

7、RL 不能用泵引理去證明一個(gè)語(yǔ)言是 RL。 (1) 由于泵引理給出的是 RL 的必要條件，所以，在用它證明一個(gè)語(yǔ)言不是 RL 時(shí)，我們使用反證法。 (2) 泵引理說(shuō)的是對(duì) RL 都成立的條件，而我們是要用它證明給定語(yǔ)言不是 RL ，這就是說(shuō)，相應(yīng)語(yǔ)言的“僅僅依賴于L的正整數(shù)N”實(shí)際上是不存在的。所以，我們一定是無(wú)法給出一個(gè)具體的數(shù)的。因此，人們往往就用符號(hào)N 來(lái)表示這個(gè)“假定存在”、而實(shí)際并不存在的數(shù)。 (3) 由于泵引理指出，如果 L 是 RL ，則對(duì)任意的 zL，只要|z|N，一定會(huì)存在u, v, w，使 uviwL 對(duì)所有的 i 成立。因此，我們?cè)谶x擇 z 時(shí)，就需要注意到論證時(shí)的簡(jiǎn)潔和

8、方便。,12,泵引理的說(shuō)明,(4) 當(dāng)一個(gè)特意被選來(lái)用作“發(fā)現(xiàn)矛盾”的 z 確定以后，就必須依照 | uv | N 和 | v |1的要求，說(shuō)明 v 不存在(對(duì)“存在u, v, w”的否定) 。 (5) 與選 z 時(shí)類似，在尋找 i 時(shí)，我們也僅需要找到一個(gè)表明矛盾的“具體”值就可以了(對(duì)“所有 i ”的否定)。 (6) 一般地，在證明一個(gè)語(yǔ)言不是 RL 的時(shí)候，我們并不使用泵引理的第(5)條。 (7) 事實(shí)上，引理所要求的 | uv | N 并不是必須的。這個(gè)限制為我們簡(jiǎn)化相應(yīng)的證明提供了良好支撐擴(kuò)充了的泵引理 。 (8) 如果希望證明一個(gè)語(yǔ)言是 RL，最直接的辦法是給出該語(yǔ)言的正則文法描述

9、，或者是 FA, RE 描述。也可以直接使用一些已有的結(jié)果和RL的性質(zhì)。,13,5.2 正則語(yǔ)言的封閉性,封閉性(closure property) 如果任意的、屬于同一語(yǔ)言類的語(yǔ)言在某一特定運(yùn)算下所得的結(jié)果仍然是該類語(yǔ)言，則稱該語(yǔ)言類對(duì)此運(yùn)算是封閉的 有效封閉性(valid closure property) 給定一個(gè)語(yǔ)言類的若干個(gè)語(yǔ)言的描述，如果存在一個(gè)算法，它可以構(gòu)造出這些語(yǔ)言在給定運(yùn)算下所獲得的運(yùn)算結(jié)果的相應(yīng)形式的語(yǔ)言描述，則稱此語(yǔ)言類對(duì)相應(yīng)的運(yùn)算是有效封閉的。 本節(jié)討論 RL 的封閉性 RL 在哪些運(yùn)算下是封閉的？,14,正則語(yǔ)言的封閉性,定理 5-1 RL 在并、乘積、閉包運(yùn)算下是

10、封閉的。 根據(jù) RE 的定義，立即可以得到此定理。 定理 5-2 RL 在補(bǔ)運(yùn)算下是封閉的。 要點(diǎn)：原來(lái)接受的不接受，不接受的接受。 證明： M =( Q, , , q0 , F ) L(M)=L， 取 DFA M = ( Q, , , q0 , Q-F ) 顯然，對(duì)于任意的 x*， (q0 , x)= f F (q0 , x)= f Q-F 即 xL(M) x L(M )， L(M )= *- L(M)。 所以， RL 在補(bǔ)運(yùn)算下是封閉的。 定理得到證明。,15,RL的交,定理 5-3 RL 在交運(yùn)算下封閉。 利用 M1M2 = (M1M2) 即可證明。 構(gòu)造 M1 = (Q1, , 1 ,

11、 q1 , F1) 和 M2 = (Q2, , 2 , q2 , F2) 的交DFA。,M = (Q1Q2 , , , (q1 , q2) , F1F2) (p, q), a) = (1(p, a), 2(q, a) ),16,RL的交,pr,1,1,S,0,qs,qr,1,0,1,ps,0,0,17,正則語(yǔ)言的封閉性,定理：如果 L 和 M 是正則語(yǔ)言，則 L- M 也是正則語(yǔ)言。 證明：利用 L-M=L M。 定理：如果 L 是正則語(yǔ)言，則 LR = x | xR L 也是正則語(yǔ)言。 構(gòu)造接受 LR 的有窮狀態(tài)自動(dòng)機(jī)： (1) 把 M 的狀態(tài)轉(zhuǎn)移圖中的所有有向邊的指向逆轉(zhuǎn)。 (2) 令 M

12、 的初始狀態(tài)為新的有窮自動(dòng)機(jī)的唯一的接受狀態(tài)。 (3) 增加一個(gè)狀態(tài) p0 為新的有窮自動(dòng)機(jī)的初始狀態(tài)，同時(shí)從該狀態(tài)出發(fā)到 M 的所有接受狀態(tài)都建立一個(gè) 轉(zhuǎn)移。,18,問(wèn)題,對(duì)字母表上的 RL L，令 DFA M = (Q, q , F ) 識(shí)別 L。 對(duì)于任意 (q, a)Q，設(shè)(q, a )=p，f (a) 是上的一個(gè)RL，假定 DFA Ma= ( Qa, ,a , q0a , Fa ) 識(shí)別 f (a)。 下面構(gòu)造 FA MRS，主框架是 M，而它的“分支子模塊”是Ma。 M 在狀態(tài) q 讀入字符 a 時(shí)進(jìn)入狀態(tài) p， 讓 MRS 在狀態(tài) q 作空移動(dòng)到 Ma 的開(kāi)始狀態(tài) q0a， 并在

13、 Ma 中處理 f (a)，之后它一定處在 Ma 的某個(gè)終止?fàn)顟B(tài)。 從 Ma 的每一個(gè)終止?fàn)顟B(tài)到 M 的狀態(tài) p 引一條標(biāo)記為的弧， 使 MRS回到狀態(tài) p。 如此下去，直到最后到達(dá) M 的終止?fàn)顟B(tài)。 可見(jiàn)，RL 在這種運(yùn)算下也是封閉的。 稱這種運(yùn)算為正則代換。,19,正則代換 (regular substitution),設(shè),是兩個(gè)字母表，映射,稱為是從 到 的代換。 如果對(duì)于a，f (a)是上的 RL ，則稱 f 為正則代換。,將 f 的定義域擴(kuò)展到*上：,(1) f ()=； (2) f (xa)=f (x) f (a)。,將 f 的定義域擴(kuò)展到,對(duì)于 L *,20,例5-4,設(shè)= 0,

14、 1 ，= a, b ，f (0)=a，f (1)=b*，則 f (010) = f (0) f (1) f (0) = ab*a f (11,00) = f (11)f (00) = f (1) f (1)f (0) f (0) = b*b*+aa = b*+aa,f (L(0*(0+1)1*) = L(a*(a+b*)(b*)*) = L(a*(a+b*)b*) = L(a*ab*+a*b*b*) = L(a*b*),21,正則代換,是正則代換, 則 (1) f ()=； (2) f ()=； (3) 對(duì)于 a，f (a) 是上的 RE； (4) 如果 r, s 是上的 RE，則 f (r

15、+s) = f (r)+f (s) f (rs) = f (r) f(s) f (r*) = f (r)* 是上的 RE。,設(shè), 是兩個(gè)字母表，映射,22,定理5-4,定理 5-4 設(shè) L 是上的一個(gè) RL，,是正則代換，則 f (L) 也是 RL。 證明思路：使用 RE 進(jìn)行定理證明。 因?yàn)?L 是RL，則存在正則表達(dá)式 r，使得 L(r)=L。 對(duì) r 中運(yùn)算符的個(gè)數(shù) n 施以歸納，證明 f (r)是表示 f (L)的 RE。 即證明：f ( L(r) ) = L( f(r) ) 當(dāng) n=0 時(shí)，結(jié)論成立。 當(dāng) nk 時(shí)定理成立，即當(dāng) r 中運(yùn)算符的個(gè)數(shù)不大于 k 時(shí)： f ( L(r)

16、) = L( f (r) )。 當(dāng) n=k+1 時(shí)， 分 3 種情況： (1) r = r1+r2(2) r = r1r2(3) r = r1*,23,定理5-4,(1) r = r1+ r2。 f (L)= f ( L(r) ) = f ( L(r1+r2) ) = f ( L(r1)L(r2) )RE 的定義 = f ( L(r1) f (L(r2) )正則代換的定義 = L( f (r1)L (f (r2) )歸納假設(shè) = L( f (r1)+f (r2)RE 的定義 = L( f (r1+r2) )RE 的正則代換的定義 = L( f (r) ),24,定理5-4,(2) r =r1r

17、2。 f (L)= f ( L(r) ) = f (L(r1r2) = f (L(r1) L(r2)RE 的定義 = f (L(r1) f (L(r2)正則代換的定義 = L(f (r1) L(f (r2)歸納假設(shè) = L( f (r1) f (r2) )RE 的定義 = L( f (r1r2) )RE 的正則代換的定義 = L( f (r) ),25,定理5-4,(3) r=r1*。 f (L)= f ( L(r) ) = f ( L(r1*) ) = f (L(r1)*)RE 的定義 = ( f (L(r1) )*正則代換的定義 = ( L(f (r1) )*歸納假設(shè) = L(f (r1)

18、*)RE 的定義 = L(f (r1*)RE 的正則代換的定義 = L( f (r) ),26,例5-5,設(shè)= 0, 1, 2 ，= a, b ，正則代換 f 定義為： f (0)=ab； f (1)=b*a*； f (2)=a*(a+b) 則： (1) f (00)=abab； (2) f (010)=abb*a*ab=ab+a+b； (3) f (0+1+2)*)=(ab+b*a*+ a*(a+b)* =(b*a*+a*(a+b)*=(a+b)*； (4) f (0(0+1+2)*)=ab(ab+b*a*+ a*(a+b)* =ab(a+b)*； (5) f (012)=abb*a*a*(

19、a+b)= ab+a*(a+b)； (6) f (0+1)*)= (ab+ b*a* )* = (ab+b+a+ b*a* )*=(a+b)* 。,27,同態(tài)映射 (homomorphism),設(shè) , 是兩個(gè)字母表，,f 為映射，如果對(duì)于 x, y*， f (xy) = f (x) f (y) 則稱 f 為從 到 * 的同態(tài)映射。,28,同態(tài)映射,對(duì)于L*，L 的同態(tài)像,對(duì)于w *，w 的同態(tài)原像是一個(gè)集合,對(duì)于 L*，L 的同態(tài)原像是一個(gè)集合,29,例5-6,設(shè)= 0, 1 ，= a, b ，同態(tài)映射 f 定義為 f (0)=aa, f (1)=aba (1) f (01)= aaaba；

20、(2) f (01)*)= (aaaba)*； (3) f -1(aab)=； (4) f -1(aa)=0； (5) f -1( aaa, aba, abaaaaa, abaaaaaa) = 1, 100 ； (6) f -1(ab+ba)*a)=1； (7) f ( f -1(ab+ba)*a)=f (1)= aba 。 令 L=(ab+ba)*a，上述(7)表明，f ( f -1(L) ) L。 可以證明 f ( f -1(L) ) L,30,RL的同態(tài)像是RL,推論5-1 RL 的同態(tài)像是 RL。 注意到同態(tài)映射是正則代換的特例，可以直接得到此結(jié)論。 該定理表明， RL 在同態(tài)映射下是

21、封閉的。 定理 5-5 RL 的同態(tài)原像是 RL 。,31,RL 的同態(tài)原像是 RL,定理 5-5 RL 的同態(tài)原像是 RL 。 證明思路：使用 DFA 作為描述工具。 接受 RL 的同態(tài)原像的 FA 的構(gòu)造思想。 讓新構(gòu)造出的 FA M 用一個(gè)移動(dòng)去模擬 M 處理 f (a) 所用的一系列移動(dòng)。 對(duì)于中的任意字符 a，如果 M 從狀態(tài) q 開(kāi)始處理 f (a)，并且當(dāng)它處理完 f (a) 時(shí)到達(dá)狀態(tài) p，則讓 M 在狀態(tài) q 讀入 a 時(shí)，將狀態(tài)變成 p。 M 具有與 M 相同的狀態(tài)，并且，在 M 對(duì)應(yīng)的狀態(tài)轉(zhuǎn)移圖中，從狀態(tài) q 到狀態(tài) p 有一條標(biāo)記為 a 的弧當(dāng)且僅當(dāng)在M的狀態(tài)轉(zhuǎn)移圖中，

22、有一條從狀態(tài) q 到狀態(tài) p 的標(biāo)記為 f (a)的路。,32,RL 的同態(tài)原像是 RL,接受 RL 的同態(tài)原像的 FA 的形式描述。 設(shè) DFA M=(Q, q0 , F )，L(M)=L， 取 DFA M =(Q, q0 , F ) (q, a)= ( q, f (a) ) 為了證明 L(M )=f -1(L(M) 只需證明，對(duì)于任意 x *， (q0 , x) F (q0 , f (x) F 為此，先證明 (q0 , x) =(q0 , f (x),33,RL 的同態(tài)原像是 RL,證明(q0 , x)=(q0 , f (x) 。 施歸納于 | x |。 當(dāng) | x | =0 時(shí)，結(jié)論顯然

23、成立。 設(shè)當(dāng) | x |=k 是結(jié)論成立，往證當(dāng) | x |=k+1 時(shí)結(jié)論成立。 不妨設(shè) x=ya，其中 | y |=k (q0 ,x)= (q0,ya) =( (q0 ,y), a) =(q0 ,f (y), a)歸納假設(shè) =(q0 ,f (y), f (a) ) 的定義 =(q0,f (y) f (a) )的意義 =(q0,f (ya)同態(tài)映射性質(zhì) =(q0,f (x),34,RL 的同態(tài)原像是 RL,這表明，結(jié)論對(duì) | x |=k+1 成立。 由歸納法原理，結(jié)論對(duì) x* 成立。 現(xiàn)在證明：x*， (q0 , x)F (q0 , f(x) F。 由于對(duì) x*， (q0 , x)=(q0

24、, f (x) )， 所以， (q0 , x)F (q0 , f (x)F。 故 L(M )=f -1( L(M) ) 定理得證。,35,商(quotient),設(shè) L1 , L2 *， L1 除以 L2 的商定義為： L1/L2= x | yL2 使得 xyL1 計(jì)算語(yǔ)言的商主要是考慮語(yǔ)言句子的后綴。 只有當(dāng) L1 的句子的后綴在 L2 中時(shí)，其相應(yīng)的前綴才屬于 L1/L2。,36,商(quotient),考慮 0, 1 上的如下語(yǔ)言： (1) L1=(0+1)*，L2=0(0+1)*，則 L1/L2=L1 (2) L1=01，L2=01，則 L1/L2= L1=(01)*，L2=(01)*

25、，則 L1/L2=L1 (3) L1=0*011*，L2=00，則 L1/L2= (4) L1=(0+1)*0，L2=(0+1)*1，則 L1/L2= (5) L1=00*1*1，L2=00*1*1，則 L1/L2=0* (6) L1=00*1*1，L2=0*1*1，則 L1/L2=0*1* 注意：(L1/L2)L2=L1 和 L1/L2 L1 不一定成立。,37,商(quotient),注意以下有意思的情況： 取L1= 000 ，并分別除以 L2=, L3=,0, L4=,0,00 , L5=, 0, 00, 000 L1/L2= 000 = L1 L1/L3= 000, 00 L1/L4=

26、 000, 00, 0 L1/L5= 000, 00, 0, 注意：在充當(dāng)“被除數(shù)”的集合不變的情況下，充當(dāng)“除數(shù)”的集合越“大”，所得的“商”可能越大。,38,L1/L2 的封閉性,定理5-6 L1 , L2*，如果 L1 是 RL ，則 L1/L2 也是 RL 。 證明：設(shè) L1 *， L1是 RL ， 則存在 DFA M1 =( Q, q0, F1)，使得 L(M1 )=L1 構(gòu)造 DFA M2 = ( Q, q0 , F2 ) 其中 F2 = q | yL2 ,(q, y)F1 顯然 L(M2 )= L1/L2。 定理得證。,39,5.3 Myhill-Nerode 定理與DFA的極小

27、化,對(duì)給定 RL L，DFA M 接受 L，M 不同，由 M 確定的*上的等價(jià)類也可能不同。 如果 M 是最小 DFA，則 M 所給出的等價(jià)類的個(gè)數(shù)應(yīng)該是最少的。 最小 DFA 是不是惟一的？如果是，如何構(gòu)造？ 最小 DFA 的狀態(tài)對(duì)應(yīng)的集合與其他 DFA 的狀態(tài)對(duì)應(yīng)的集合有什么樣的關(guān)系，用這種關(guān)系是否能從一般的 DFA 出發(fā)，求出最小 DFA？,40,關(guān)系 RM,設(shè) DFA M =( Q, , q0 , F )。 M 確定的*上的關(guān)系 RM 為： 對(duì)于 x , y* x RM y (q0 , x)=(q0 ,y)。 顯然，x RM y qQ, x, yset(q) 因此，RM 決定了* 的一

28、個(gè)分類。,41,例5-8,設(shè) L=0*10*，它對(duì)應(yīng)的 DFA M 如右圖所示。,對(duì)應(yīng)于q0：(00)n RM (00)mn, m0； 對(duì)應(yīng)于q1：0(00)n RM 0(00)mn, m 0； 對(duì)應(yīng)于q2：(00)n1 RM (00)m1n, m 0； 對(duì)應(yīng)于q3：0(00)n 1 RM 0(00)m1n, m 0； 對(duì)應(yīng)于q4： 0(00)n 10k RM 0(00)m10hn, m 0, k, h 1； (00)n10k RM (00)m10hn, m 0, k, h 1； 0(00)n 10k RM (00)m10hn, m 0, k, h 1； 即： 0n 10k RM 0m10hn

29、, m 0, k, h1； 對(duì)應(yīng)于q5：x RM yx, y 為至少含兩個(gè) 1 的串。,42,關(guān)系 RL,L 確定的 *上的關(guān)系 RL。 對(duì)于 x, y*， x RL y ( 對(duì)z*，xzL yzL) 即：對(duì)于 x, y*，如果 x RL y，則在 x 和 y 后無(wú)論接*中的任何串 z，xz 和 yz 要么都是 L 的句子，要么都不是L 的句子。,43,關(guān)系 RM 與關(guān)系 RL,如果 L 是一個(gè) RL，DFA M 接受的語(yǔ)言是 L，對(duì)于qQ，set(q)中的任意兩個(gè)串x, y，必有 xRLy 成立，即xRL(M) y。 由于 x, yset(q)，所以(q0 , x)=(q0 , y)=q 對(duì)

30、于z*， (q0 , xz)=(q0 , x), z) =(q, z) =(q0 , y) , z) =(q0, yz) 這就是說(shuō)，(q0 , xz)F (q0 , yz)F 即對(duì)于z*，xzL yzL。 表明，x RL y，也就是 x RL(M) y。,如果 xRM y，則必有 xRL(M) y。 如果 xRL(M) y，則不一定有 xRM y。,44,例,設(shè) L=0*10*，它對(duì)應(yīng)的 DFA M 如右圖所示。,對(duì)應(yīng)于q0：(00)n RM (00)mn, m0； 對(duì)應(yīng)于q1：0(00)n RM 0(00)mn, m 0； 對(duì)應(yīng)于q2：(00)n1 RM (00)m1n, m 0； 對(duì)應(yīng)于q

31、3：0(00)n 1 RM 0(00)m1n, m 0； 對(duì)應(yīng)于q4： 0n 10k RM 0m10hn, m 0, k, h1； 對(duì)應(yīng)于q5：x RM yx, y 為至少含兩個(gè) 1 的串。,00set(q0)， 0set(q1)， 0 RM 00不成立，但 0 RL(M) 00 成立。,45,右不變關(guān)系,右不變的 (right lnvariant) 等價(jià)關(guān)系 設(shè) R 是*上的等價(jià)關(guān)系，對(duì)于 x, y*，如果 xRy，則必有 xz R yz 對(duì)于 z*成立，則稱 R 是右不變的等價(jià)關(guān)系。,46,命題5-1,命題 5-1 對(duì)于任意 DFA M = ( Q, q0 , F )，M 所確定的*上的關(guān)

32、系 RM 為右不變的等價(jià)關(guān)系。 證明： (1) RM 是等價(jià)關(guān)系。 自反性： 因?yàn)? q0 , x ) =( q0 , x )，所以 x RM x 。 對(duì)稱性：x, y*， x RM y ( q0 , x ) =( q0 , y )根據(jù) RM 的定義； ( q0 , y ) =( q0 , x )“=”的對(duì)稱性； y RM x根據(jù) RM 的定義。,47,命題5-1,傳遞性：設(shè) x RM y，y RM z。 由于 x RM y，(q0 ,x) =(q0 ,y) 由于 y RM z，(q0 ,y) =(q0 , z) 由 “=” 的傳遞性知， (q0 ,x) =(q0 ,z) 再由 RM 的定義得

33、： x RM z 綜上，RM 是等價(jià)關(guān)系。,48,命題5-1,(2) RM是右不變的 設(shè) x RM y，則(q0 , x)=(q0 , y)=q 所以，對(duì)于z*， (q0 , xz)=(q0 , x), z) =(q, z) =(q0 , y), z) =(q0 , yz) 由 RM 的定義， xz RM yz 所以， RM 是右不變的等價(jià)關(guān)系。,49,命題5-2,命題 5-2 對(duì)于任意 L *，L 所確定的*上的關(guān)系 RL 為右不變的等價(jià)關(guān)系 。 證明： (1) RL是等價(jià)關(guān)系。 自反性顯然。 對(duì)稱性：不難看出： x RL y (對(duì) z*，xzL yzL ) y RL x 傳遞性：設(shè) x R

34、L y，y RL z。 x RL y ( 對(duì) w*，xwL ywL ) y RL z ( 對(duì) w*，ywL zwL ) 所以，(w*,xwL ywL 且 ywL zwL ) 即：(對(duì)w*，xwL zwL) 故：x RL z 即 RL 是等價(jià)關(guān)系。,50,命題5-2,(2) RL 是右不變的。 設(shè) x RL y。由 RL 的定義，對(duì) w, v*， xwvL zwvL，注意到 v 的任意性，知 xw RL yw。 所以， RL 是右不變的等價(jià)關(guān)系。,51,指數(shù)(index),設(shè) R 是*上的等價(jià)關(guān)系，則稱 |*/R| 是 R 關(guān)于*的指數(shù)。簡(jiǎn)稱為 R 的指數(shù)。 * 的關(guān)于R 的一個(gè)等價(jià)類，也就是*

35、/R 的任意一個(gè)元素，簡(jiǎn)稱為 R 的一個(gè)等價(jià)類 。,52,例5-9,右圖所給 DFA M 所確定的 RM 的指數(shù)為 6。 RM 將*分成 6 個(gè)等價(jià)類： set(q0)= (00)n | n0 ； set(q1)= 0(00)n | n0 ； set(q2)= (00)n1 | n, m0 ； set(q3)= 0(00)n 1| n0 ； set(q4)= 0n10k | n0, k1 ； set(q5)= x | x 為至少含兩個(gè) 1 的串。,53,RM 與 RL(M),x, y*，如果 x RM y，必有 xRL(M) y 成立。 對(duì)于任意 DFA M=(Q, q0, F)： (1) |

36、*/ RL(M) |*/RM|Q| (2) 按照 RM 中被分在同一等價(jià)類的串，在按照 RL(M) 分類時(shí)，一定會(huì)被分在同一個(gè)等價(jià)類。 RM對(duì) * 的劃分比 RL(M) 對(duì) * 的劃分更“細(xì)”。 稱 RM 是 RL(M) 的“加細(xì)”(refinement)。,54,問(wèn)題討論,在*/RM = set(q0), set(q1), set(q2), set(q3), set(q4), set(q5) 中， 是否存在有根據(jù) RL(M) 可以“合并” 的等價(jià)類？ (1) 取 00set(q0)，000set(q1)。 對(duì)于任意的 x*， 當(dāng) x 含且只含一個(gè) 1 時(shí)，00 xL(M)，000 xL(M)

37、； 當(dāng) x 不含 1 或者含多個(gè) 1 時(shí)，00 xL(M)，000 xL(M)。 這就是說(shuō)，對(duì)于任意 x*，00 xL(M) 000 xL(M)。即按照 RL(M)，00 與 000 被分在同一個(gè)等價(jià)類中。 從而 set(q0) 和 set(q1) 被包含在 RL(M) 的同一個(gè)等價(jià)類中。,55,問(wèn)題討論,(2) 取 00set(q0)，001set(q2)。 取特殊的字符串1*，001L(M)，但0011L(M)。所以，根據(jù) RL(M)，set(q0) 和 set(q2)不能被“合并”到一個(gè)等價(jià)類中。 類似地，根據(jù) RL(M)，set(q3)、set(q4)、set(q5) 也都不能被“合并

38、”到 set(q0) 的句子所在的等價(jià)類中。 (3) 取 001set(q2)，01set(q3)。 對(duì)于任意的 x*，x 要么不含 1，要么含有 1。 當(dāng) x 不含 1 時(shí)，001xL(M)，01xL(M)； 當(dāng) x 含有 1 時(shí)，001xL(M)，01xL(M)。 這就是說(shuō)，對(duì)于任意 x*，001xL(M) 01xL(M)。即按照 RL(M)，001 與 01 屬于 RL(M) 的同一個(gè)等價(jià)類中。從而set(q2) 和 set(q3) 被包含在 RL(M) 的同一個(gè)等價(jià)類中。,56,問(wèn)題討論,(4) 取 1set(q2)， 10set(q4)。 對(duì)于任意的 x*，x 要么不含 1，要么含有

39、 1。 當(dāng) x 不含 1 時(shí)，1xL(M)，10 xL(M)； 當(dāng) x 含有 1 時(shí)，1xL(M)，10 xL(M)。 這就是說(shuō)，對(duì)于任意的 x*，1xL(M) 10 xL(M)。即按照 RL(M)，1 與 10 被分在 RL(M) 的同一個(gè)等價(jià)類中。 從而在 set(q2) 和 set(q4) 被包含在 RL(M) 的同一個(gè)等價(jià)類中。 (5)取 1set(q2)， 11set(q5)。 注意到 1=1，11=11；而1L(M)，11L(M)。即 1 和 11不滿足關(guān)系 RL(M)，所以，set(q2) 和 set(q5) 不能被“合并”到RL(M) 的同一個(gè)等價(jià)類中。在這里，* 是一個(gè)特殊的

40、字符串。,57,問(wèn)題討論,*/RL(M)= set(q0)set(q1)，set(q2)set(q3)set(q4)，set(q5) 不含 1： 0= set(q0)set(q1) = 0*； 含一個(gè) 1： 1= set(q2)set(q3)set(q4) = 0*10*； 含多個(gè) 1： 11= set(q5) = 0*10*1(0+1)* 。,58,Myhill-Nerode 定理,米希爾-尼德羅定理 如下三個(gè)命題等價(jià)： (1) L *是 RL 。 (2) L 是 * 上的某一個(gè)具有有窮指數(shù)的右不變等價(jià)關(guān)系 R 的某些等價(jià)類的并。 (3) RL 具有有窮指數(shù)。,59,由(1)可以推出(2),

41、(1) L *是 RL 。 (2) L 是 * 上的某一個(gè)具有有窮指數(shù)的右不變等價(jià)關(guān)系 R 的某些等價(jià)類的并。 設(shè) L *是 RL ， 所以，存在 DFA M = ( Q, q0, F )，使得 L(M)=L。 由命題5-1，RM 是 * 上的右不變等價(jià)關(guān)系， 而且 |*/RM | Q |，所以，RM 具有有窮指數(shù)。而,即 L 是 * 上的具有有窮指數(shù)的右不變等價(jià)關(guān)系 RM 的、對(duì)應(yīng)于 M 的終止?fàn)顟B(tài)的等價(jià)類的并。,60,由(2)可以推出(3),(2) L 是 * 上的某一個(gè)具有有窮指數(shù)的右不變等價(jià)關(guān)系 R 的某些等價(jià)類的并。 (3) RL 具有有窮指數(shù)。 設(shè) xRy，由 R 的右不變性可知，

42、對(duì)于任意 z*， xzRyz 而 L 是 R 的某些等價(jià)類的并，所以 xzL yzL 根據(jù) RL 的定義， xRL y 故 R 是 RL 的加細(xì)。 由于 R 具有有窮指數(shù)，所以，RL 具有有窮指數(shù)。,61,由(3)可以推出(1),(3) RL 具有有窮指數(shù)。 (1) L * 是 RL 。 設(shè) RL 具有有窮指數(shù)。往證存在 DFA M ，使得 L(M )=L。 思路是用等價(jià)類對(duì)應(yīng)狀態(tài)，狀態(tài)之間的轉(zhuǎn)移依據(jù)相應(yīng)的等價(jià)類的變化。 令 M =(*/RL, , , , x | xL ) 表示所在的等價(jià)類對(duì)應(yīng)的狀態(tài)； x 表示 x 所在的等價(jià)類對(duì)應(yīng)的狀態(tài)。 對(duì)于 (x, a)(*/RL), (x, a) =

43、 xa 定義具有相容性 (如果x=y，那么 xa=ya) 如果 x 和 y 同處一個(gè)等價(jià)類，即 x=y，有 xRLy， 由 RL 的右不變性，有 xaRLya 即 xa=ya。 因此，L(M )=L。,62,例5-10,用定理5-7證明 0n1n | n0 不是 RL。 思路：根據(jù) L 的句子的特征來(lái)尋找 RL 的等價(jià)類。 L 的句子的主要特點(diǎn)有兩個(gè)： (1) 句子中所含的字符 0 的個(gè)數(shù)與所含的字符 1 的個(gè)數(shù)相同。 (2) 所有的 0 都在所有的 1 的前面。 由此可知，對(duì)所有的串 x，如果 x 是 0n1m ( mn+1)，或者 x 中含有子串10，則無(wú)論 x 后面接任何串 z，都有 x

44、z 不屬于L。 將此等價(jià)類記為 10。 再考慮形如 0n 形如 0n1m 的串， m, n0 且 n m。 注意到 01L，001L，所以 0 和 00 不在同一個(gè)等價(jià)類中。 可以得到如下一些等價(jià)類。,63,例5-10,10= x | x=0n1m (mn+1) 或者 x 中含子串 10 所在的等價(jià)類； 10 所在的等價(jià)類； 200 所在的等價(jià)類； 3000 所在的等價(jià)類； n0n 所在的等價(jià)類； 所以，RL 的指數(shù)是無(wú)窮的。因此，L 不是 RL。,64,Myhill-Nerode 定理的推論,推論 5-2 對(duì)于任意的 RL L，如果 DFA M=(Q, q0 , F) 滿足 L(M)=L，則

45、|*/RL|Q|。 即 對(duì)于任意DFA M=(Q, q0, F)，|Q|*/RL(M)|。 也表明，對(duì)任意一個(gè) RL L，按照定理5-7中所給的方法構(gòu)造出來(lái)的DFA M 是一個(gè)接受 L 的最小DFA。 問(wèn)題：這個(gè) DFA 是惟一的么？ 推論5-3 對(duì)于任意的 RL L，在同構(gòu)意義下，接受 L 的最小DFA是惟一的。 接受 L 的最小 DFA M=(Q, , q0 , F) 定理5-7 構(gòu)造的 DFA M =(*/RL, , , , x | xL ) M 與 M 同構(gòu)，是指二者的狀態(tài)數(shù)一一對(duì)應(yīng)，狀態(tài)轉(zhuǎn)移也是一一對(duì)應(yīng)的。 定義映射：f (q)=f (q0 , x) )= ( , x )=x 即讓

46、M 的狀態(tài) x 與 M 的狀態(tài) q=(q0 , x) 對(duì)應(yīng)， 該狀態(tài)正是 x 引導(dǎo) M 從 q0 出發(fā)所到達(dá)的狀態(tài)。,65,推論5-3,推論5-3 對(duì)于任意的 RL L，在同構(gòu)意義下，接受 L 的最小DFA 是惟一的。 證明： 接受 L 的最小 DFA M = (Q, q0 , F) 的狀態(tài)數(shù)與 RL 的指數(shù)相同，也就是說(shuō)，這個(gè)最小 DFA 的狀態(tài)數(shù)與 Myhill-Nerode 定理證明中構(gòu)造的 M =(*/RL, , , x | xL )的狀態(tài)數(shù)是相同的。 DFA 同構(gòu)是指這兩個(gè) DFA 的狀態(tài)之間有一個(gè)一一對(duì)應(yīng)，而且這個(gè)一一對(duì)應(yīng)還保持狀態(tài)轉(zhuǎn)移也是相應(yīng)一一對(duì)應(yīng)的。也就是說(shuō)，如果 q 與 w

47、 對(duì)應(yīng)，p 與 z 對(duì)應(yīng)，當(dāng)(q, a)=p時(shí)，必定有(w, a)=z。 這兩個(gè) DFA 是同構(gòu)。定義映射 f f (q)=f (q0 , x) )= ( , x)=x 即讓 M 的狀態(tài) x 與 M 的狀態(tài) q=(q0 , x)對(duì)應(yīng)， 該狀態(tài)正是 x 引導(dǎo) M 從 q0 出發(fā)所到達(dá)的狀態(tài)。,66,推論5-3,往證 f 為 Q 與 */RL 之間的一一對(duì)應(yīng)。 如果(q0 ,x)=(q0 ,y)，則 xRM y 由于 RM 是 RL 的加細(xì)，所以，x RL y 故，x=y，即(, x)=(, y)。 如果(q0 ,x)(q0 ,y) 則 (，x) (, y) 即xy 否則|*/RM |*/RL |

48、。 這與 M 是最小 DFA 矛盾。 所以，f 是 Q 與 */RL 之間的一一對(duì)應(yīng)。,67,推論5-3,往證，如果(q, a)=p，f (q)=f (q0,x)=x， 由于 (, xa)=xa，因此必有 f (p)=xa。 事實(shí)上，對(duì)于 qQ， 如果f (q) = f (q0,x)=x 則對(duì)于 a，如果 p=(q, a)=(q0,x), a)=(q0,xa ) 則 f (p)=f (q, a)= f (q0 ,x), a)=f (q0 ,xa)=xa 即如果 M 在狀態(tài) q 讀入字符 a 時(shí)進(jìn)入狀態(tài) p， 則 M 在 q 對(duì)應(yīng)的狀態(tài) f (q0 ,x)=x 讀入字符 a 時(shí)，進(jìn)入 p 對(duì)應(yīng)的

49、狀態(tài) f (q0 ,xa) )=xa。 所以，f 是 M 和 M 之間的同構(gòu)映射。,68,DFA的極小化,對(duì)于任給的 RL L，接受 L 的最小 DFA 是唯一的。 按照 L 所決定的等價(jià)關(guān)系 RL 的等價(jià)類來(lái)設(shè)立狀態(tài)和狀態(tài)之間的轉(zhuǎn)移函數(shù)是構(gòu)造最小 DFA 的一種方法。 計(jì)算機(jī)求解困難 對(duì)于 RL L，如果有一個(gè) DFA M，使得 L(M)=L，可以通過(guò)合并 RM 的等價(jià)類來(lái)求出 RL 的等價(jià)類。注意這些等價(jià)類對(duì)應(yīng)的是狀態(tài)。 做法：分別從 set(q) 和 set(p) 中各取一個(gè)利于考察的“適當(dāng)”字符串 x, y，然后研究對(duì)于任意的 z，xz 和 yz 同時(shí)屬于L 或者同時(shí)不屬于 L。 具有

50、較高的復(fù)雜性,69,DFA的極小化,考慮哪些狀態(tài)不可以合并。 (1)Q-F 中的任意狀態(tài)和 F 中的任意狀態(tài)是不能合并的。 設(shè) qQ-F，pF，xset(q)，yset(p)， 則有 x不屬于 L，而 y屬于 L，x 和 y 不滿足關(guān)系 RL， 所以 q 和 p 不能合并。 由此得到第一批不能合并的狀態(tài)對(duì)。 (2) 考察其它不知能否合并的狀態(tài)對(duì) q 和 p 。 如果 中存在字符 a，使得(q, a)=q，(p, a)=p， 則 q 和 p 也是不能合并的。 當(dāng)找出所有的不可以合并的狀態(tài)對(duì)后，剩余的狀態(tài)對(duì)就是可以合并的了。,70,可區(qū)分狀態(tài),可以區(qū)分的 (distinguishable) 狀態(tài)

51、設(shè) DFA M = ( Q, q0 , F )，如果 x*， 對(duì) Q 中的兩個(gè)狀態(tài) q 和 p，使得 (q, x)F 和(p, x)F 中，有且僅有一個(gè)成立，則稱 p 和 q 是可以區(qū)分的。 否則，稱 q 和 p 等價(jià)。并記作 qp 。,71,DFA的極小化算法,算法5-1 DFA 的極小化算法 算法思想：掃描所有的狀態(tài)對(duì)，找出所有的可區(qū)分的狀態(tài)對(duì)，不可區(qū)分的狀態(tài)對(duì)一定是等價(jià)的。 輸入：給定的 DFA。 輸出：可區(qū)分狀態(tài)表。 主要數(shù)據(jù)結(jié)構(gòu)：狀態(tài)對(duì)的關(guān)聯(lián)鏈表，可區(qū)分狀態(tài)表。,72,DFA的極小化算法,主要步驟 (1) for (q, p)F(Q-F) do 標(biāo)記可區(qū)分狀態(tài)表中的表項(xiàng) (q, p)

52、；/ p 和 q 不可合并 (2) for (q, p)FF(Q-F) (Q-F) & qp do (3) if a，可區(qū)分狀態(tài)表中的表項(xiàng)(q,a),(p,a)已被標(biāo)記 then begin (4) 標(biāo)記可區(qū)分狀態(tài)表中的表項(xiàng)(q, p)； (5) 遞歸地標(biāo)記本次被標(biāo)記的狀態(tài)對(duì)的關(guān)聯(lián)鏈表上的各個(gè)狀態(tài)對(duì)在可區(qū)分狀態(tài)表中的對(duì)應(yīng)表項(xiàng) end (6) else for a，do (7) if (q,a)(p,a) &(q,p)與(q,a),(p,a)不是同一個(gè)狀態(tài)對(duì) then 將(q,p)放在(q,a),(p,a)的關(guān)聯(lián)鏈表上。,73,定理5-8,定理5-8 對(duì)于任意DFA M=(Q,q0 , F)，Q

53、中的兩個(gè)狀態(tài)q和p是可區(qū)分的充要條件是(q,p)在DFA的極小化算法中被標(biāo)記。 必要性的證明。 設(shè)q和p是可區(qū)分的，x是區(qū)分q和p的最短字符串?，F(xiàn)施歸納于x的長(zhǎng)度，證明(q，p)一定被算法標(biāo)記。 當(dāng)|x|=0時(shí) 區(qū)分q和p，表明q和p有且僅有一個(gè)為M的終止?fàn)顟B(tài)，所以，(q,p)F(Q-F) 因此，它在算法的第(1)行被標(biāo)記。 設(shè)當(dāng)|x|=n時(shí)結(jié)論成立 x是區(qū)分q和p的長(zhǎng)度為n的字符串，則(q,p)被算法標(biāo)記。,74,定理5-8,當(dāng)|x|=n+1時(shí) 設(shè)x=ay，其中|y|=n。由于x是區(qū)分q和p的最短的字符串，所以，(q,x)F 和(p,x)F中，有且僅有一個(gè)成立。 不妨假設(shè)：(q,x)F ，(

54、p,x)F 即(q,a)，y)F ，(p,a),y)F 設(shè)(q,a)=u，(p,a)=v y是區(qū)分u和v的長(zhǎng)度為n的字符串。 由歸納假設(shè)，(u,v)可以被算法標(biāo)記。 如果在考察(q,p)時(shí)，(u,v)已經(jīng)被標(biāo)記，則(q,p)在算法的第(4)行被標(biāo)記； 如果在考察(q,p)時(shí)，(u,v)還沒(méi)有被標(biāo)記，則(q,p)在算法的第(7)行被放入到(u,v)的關(guān)聯(lián)鏈表中，而當(dāng)(u,v)被標(biāo)記時(shí)，在算法的第(5)行在“遞歸”過(guò)程中(q,p)被標(biāo)記。 結(jié)論對(duì)|x|=n+1成立。,75,定理5-8,充分性的證明。 設(shè)(q,p)在算法中被標(biāo)記。對(duì)它被標(biāo)記的順序n施歸納，證明q和p是可區(qū)分的。 令|F(Q-F)|=

55、m，顯然，當(dāng)1nm時(shí)，(q,p)是在算法的第(1)行被標(biāo)記的，此時(shí)，是區(qū)分q和p的字符串： (q,)F 和(p,)F 有且僅有一個(gè)成立。 設(shè)nk(km)時(shí)結(jié)論成立。即，如果 (q,p)是被算法在第k個(gè)或者第k個(gè)之前標(biāo)記的，則存在字符串x，x區(qū)分q和p。即：(q,x)F 和(p,x)F有且僅有一個(gè)成立。,76,定理5-8,當(dāng)n=k+1時(shí)，如果(q,p)是在算法的第(4)行被標(biāo)記的，此時(shí)，(q,a),(p,a)一定是在第k個(gè)之前被標(biāo)記的。設(shè)(q,a)=u，(p,a)=v，由歸納假設(shè)，存在字符串x，x區(qū)分u和v： (u,x)F 和(v,x)F 有且僅有一個(gè)成立，從而， (q,ax)F 和(p,ax)

56、F 有且僅有一個(gè)成立。即，ax是區(qū)分q和p的字符串。 如果(q,p)是在算法的第(5)行被標(biāo)記的，則它必在某個(gè)狀態(tài)對(duì)(u,v)的關(guān)聯(lián)鏈表中，而(u,v)必在(q,p)之前被標(biāo)記。由歸納假設(shè)，存在x區(qū)分(u，v)； 存在a，(q,a)=u，(p,a)=v使得(q,p)被放在(u,v)的關(guān)聯(lián)鏈表中；ax是區(qū)分q和p的字符串。 所以，結(jié)論對(duì)n=k+1成立。由歸納法原理，結(jié)論對(duì)所有的n成立。,77,定理5-9,定理5-9 由算法5-1構(gòu)造的DFA在去掉不可達(dá)狀態(tài)是最小DFA 。 證明： 設(shè)M=(Q,q0,F)為算法5-1的輸入DFA， M =(Q/, , q0,F )是相應(yīng)的輸出DFA。 F =q|q

57、F。 對(duì)于 qQ/， a，定義 (q,a)=(q,a),78,定理5-9, 的相容性。 設(shè)q=p ，也就是說(shuō)，q和p等價(jià)：qp。即根據(jù)算法5-1，狀態(tài)q和p是不可區(qū)分的(未被算法標(biāo)記)。此時(shí)，對(duì)于 a，必須有(q,a)(p,a)。否則，狀態(tài)對(duì)(q,a)，(p,a)必定被算法標(biāo)記，從而最終導(dǎo)致(q，p)被算法標(biāo)記。此與qp矛盾。所以，狀態(tài)(q,a)和狀態(tài)(p,a) 等價(jià)：(q,a)=(p,a)。所以， 的定義是相容的。,79,定理5-9,L(M )=L(M) 。 對(duì)x*，現(xiàn)施歸納于|x|，證明 (q0,x)=(q0,x) |x|=0 (q0,)=q0=(q0 ,) x*并且|x|=n， (q0，

58、xa)=(q0,x),a) =(q0 ,x),a) =(q0 ,x),a) =(q0 ,xa) 由歸納法原理，結(jié)論對(duì)x*成立。,80,定理5-9,再由F 的定義， (q0,x)=(q0 ,x)F (q0,x)F。 所以， xL(M) xL(M)。 即： L(M )=L(M)。,81,定理5-9,證明所構(gòu)造的M 去掉不可達(dá)狀態(tài)后是最小DFA。 如果qp，則對(duì)于xset(q)，yset(p)，x RL y不成立。事實(shí)上，如果qp，則存在z*，z區(qū)分q和p，有(q,z)=q 和(p,z)= p 有且僅有一個(gè)是終止?fàn)顟B(tài)，這就是說(shuō)，xz和yz有且僅有一個(gè)是L的句子。所以，x RL y是不成立的。,82,例5-11,用算法 5-1 對(duì)下圖所給的 DFA 進(jìn)行極小化。,83,例5-12,用算法 5-1 對(duì)下圖所給的 DFA 進(jìn)行極小化。,84,例5-12,85,5.4 關(guān)于正則語(yǔ)言的判定算法,正則語(yǔ)言的表示