第05章正則語言的性質(zhì)-28、29、30節(jié)課-2013-11-12

研究動機{0n1n|n

1}不是RL。不具有RL的性質(zhì)，因此不存在RG，F(xiàn)A，RE等的形式描述。RL有什么性質(zhì)？對給定的RL，能否/如何找到最小的DFA？？第5章正則語言的性質(zhì)5.1正則語言的泵引理5.2正則語言的封閉性5.3Myhill-Nerode定理與DFA的極小化5.4關(guān)于正則語言的判斷算法5.5小結(jié)第5章

正則語言的性質(zhì)RL性質(zhì)泵引理及其應(yīng)用

并、乘積、閉包、補、交、正則代換、同態(tài)、逆同態(tài)的封閉性

從RL固有特征尋求表示的一致性Myhill-Nerode定理FA的極小化

RL的幾個判定問題空否、有窮否、兩個DFA等價否、成員關(guān)系

5.1正則語言的泵引理任何有窮語言都是RL逆否命題：非RL一定是無窮語言問題：無窮語言是否一定不是RL？？？解決方案：從RL的“本質(zhì)”特征出發(fā)5.1正則語言的泵引理DFA是RL的識別模型。一個DFA只有有窮個狀態(tài)，當該DFA識別的語言L是無窮語言時，L中必定存在一個足夠長(大于DFA的可達狀態(tài)數(shù))的句子，使得DFA在識別該句子的過程中，肯定要重復(fù)地經(jīng)過某一狀態(tài)。5.1正則語言的泵引理如句子z=a1a2…

am

，假設(shè)DFAM在識別它的過程中經(jīng)過的狀態(tài)依次為q0q1…

qm，根據(jù)鴿籠原理，則當m大于M的可達狀態(tài)數(shù)時，這些狀態(tài)至少有一對是重復(fù)的，不妨令為qk和qj，顯然kj。泵引理推導(dǎo)示意圖Sa1q0q1qka2…akak+1…ajqjaj+1…amqmSa1q0q1qk=qja2…akak+1…ajaj+1…amqm泵引理證明設(shè)L是一個RL，DFAM=(Q,,,q0,F)滿足L(M)=L，|Q|=N，并假設(shè)M中不含任何不可達狀態(tài)。取L的句子z=a1a2…am(m

N)對h

[1..m]，令(q0,a1a2…ah)=qh由于m

N

，所以k,j[0..N],k

<j且qk=qj泵引理證明(續(xù))此時有(q0,a1a2…ak)=qk(qk,ak+1…aj)=qj=qk(qj,aj+1…am)=qm所以對于非負整數(shù)i(qk,(ak+1…aj)i)=(qk,(ak+1…aj)i-1)=…=(qk,ak+1…aj)=qkSa1q0q1qka2…akak+1…ajqjaj+1…amqm泵引理證明(續(xù))因為zL(M)，所以qmF而(q0,a1a2…ak(ak+1…aj)iaj+1…am)=qmF所以a1a2…ak(ak+1…aj)iaj+1…amL(M)

取u=a1a2…akv=ak+1…ajw=aj+1…am有：對非負整數(shù)i,uviwL注意到j(luò)

N,k<j,有：|uv|

N,|v|1Sa1q0q1qka2…akak+1…ajqjaj+1…amqm引理5-1設(shè)L為一個RL，則存在僅依賴于L的正整數(shù)N，對于zL，如果|z|N，則u，v，w，st.(1)z=uvw(2)|uv|N(3)|v|1(4)對于整數(shù)i0，uviwL(5)N不大于接受L的最小DFAM的狀態(tài)數(shù)例5-1證明{0n1n|n1}不是RL。證明：令L={0n1n|n1}

。假設(shè)L是RL，則它滿足泵引理。不妨設(shè)N是泵引理中僅依賴于L的正整數(shù)，取

z

=

0N1N，顯然zL此時必然u,v,wst.z=uvw,|uv|N,

|v|1，因此v只可能是由0組成的非空串設(shè)v=0k，

k1

;w=0j1N則u=0N-k-j例5-1(續(xù))從而有

uviw=0N-k-j(0k)i0j1N

當i=2時，uv2w=0N-k-j02k0j1N=0N+k1N由于k1，N+k>N

也就是說，uv2w

L，這與泵引理矛盾。所以，L不是RL。例5-2例5-2證明{0n|n為素數(shù)}不是RL。證明：假設(shè)L={0n|n為素數(shù)}是RL。取z=0N+p∈L，不妨設(shè)v=0k， k≥1，w=0j

從而有，

uviw=0N+p-k-j(0k)i0j

=0N+p+(i-1)k例5-2（續(xù)）當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)注意到k≥1，所以

N+p+(N+p+1-1)k=(N+p)(1+k)不是素數(shù)。故當i=N+p+1時，uvN+p+1w=0(N+p)(1+k)

L這與泵引理矛盾。所以，L不是RL。例5-3證明{0n1m2n+m|m,n1}不是RL。證明：令L={0n1m2n+m|m,n1}

。假設(shè)L是RL，則它滿足泵引理。不妨設(shè)N是泵引理中僅依賴于L的正整數(shù)，取

z

=

0N1N22N，顯然zL此時必然u,v,wst.z=uvw,|uv|N,

|v|1，因此v只可能是由0組成的非空串設(shè)v=0k，

k1

;w=0j1N22N則u=0N-k-j例5-3(續(xù))從而有

uviw=0N-k-j(0k)i0j1N22N

當i=0時，uv0w=0N-k1N22N由于k1，N–k+N<2N

也就是說，uv0wL，這與泵引理矛盾。所以，L不是RL。例5-3(續(xù))注意：本例與例5-1非常相似。實際上，證明一個語言不是RL的題都需要相同的步驟（模板）。雖然取z

=

0N1N22N，但當0串被泵進/泵出時，應(yīng)說明它不滿足0n1m2n+m，而不是0n1n22n。泵引理的注意事項用來證明一個語言不是RL不能用泵引理去證明一個語言是RL。

(1)由于泵引理給出的是RL的必要條件，所以，在用它證明一個語言不是RL時，我們使用反證法。(2)由于泵引理指出，如果L是RL，則對任意的z∈L，只要|z|≥N，一定會存在u、v、w，使uviw∈L對所有的i成立。因此，我們在選擇z時，就需要注意到論證時的簡潔和方便。(3)當一個特意被選來用作“發(fā)現(xiàn)矛盾”的z確定以后，就必須依照|uv|≤N和|v|≥1的要求，說明v不存在(對“存在u、v、w”的否定)。作業(yè)(見習(xí)題)2.(1)(3)(8)5.2正則語言的封閉性定義5-1

如果任意的、屬于某一語言類的語言在某一特定運算下所得的結(jié)果仍然是該類語言，則稱該語言類對此運算是封閉的，并稱該語言類對此運算具有封閉性(closureproperty)。我們所熟悉的封閉性：整數(shù)對于加法是封閉的，有理數(shù)對于乘法/除法是封閉的。有效封閉性給定一個語言類的若干個語言的描述。如果存在一個算法，它可以構(gòu)造出這些語言在給定運算下所獲得的運算結(jié)果的相應(yīng)形式的語言描述，則稱此語言類對相應(yīng)的運算是有效封閉的，并稱此語言類對相應(yīng)的運算具有有效封閉性(validclosureproperty)。定理5-1RL在并、乘積、閉包運算下是封閉的。根據(jù)RE的定義，立即可以得到此定理。定理5-2RL在補運算下是封閉的。補：兩個DFA具有互補的終止狀態(tài)。如果DFAM=(Q,,,q0,F)識別的語言為L，那么DFAM'=(Q,,,q0,Q–F)識別的語言應(yīng)為*–L。定理5-2（續(xù)）RL在補運算下是封閉的。證明：(補：兩個DFA具有互補的終止狀態(tài)。)M=(Q，∑，δ，q0，F(xiàn))，L(M)=L，取DFAM′=(Q，∑，δ，q0，Q-F)

顯然，對于任意的x∈∑*，

δ(q0，x)=f∈Fδ(q0，x)=fQ-F

即：x∈L(M)xL(M′)，

L(M′)=∑*-L(M)。所以，RL在補運算下是封閉的。定理得到證明。定理5-3RL在交運算下是封閉的。交：同時滿足兩個RL。證明：由定理5-1（RL在并、乘積、閉包運算下是封閉的），定理5-2（RL在補運算下是封閉的）及DeMorgan定理可得。定義5-2設(shè),

是兩個字母表，映射f:2*稱為是從到的代換(substitution)。如果對于a

，f(a)是上的RL，則稱f為正則代換(regularsubstitution)。復(fù)習(xí)：*是指字母表上的克林閉包，即中若干個字符連接而成字符串的集合(P30)；而2*是指*的冪集(P10)擴展先將f的定義域擴展到*上：f:*2*(1)f()={}(允許空字符)(2)f(xa)=f(x)f(a)(允許字符串)再將f的定義域擴展到2*上：f:2*2*對于L*，

f(L)=f(x)(允許字符串集合，即語言)例5-4設(shè)

={0,1},={a,b},f(0)=a,f(1)=b*，(注意沒有嚴格區(qū)分a與{a},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定義5-3設(shè),

是兩個字母表，映射f:2*為正則代換，則(1)f(?)=?(2)f()=

(3)對于a，f(a)

是上的正則表達式(4)如果r,s是上的正則表達式，則f(r+s)=f(r)+f(s)f(rs)=f(s)f(s)f(r*)=f(r)*是上的正則表達式定理5-4設(shè)L是上的一個RL,

f:2*為正則代換，則f(L)也是RL。證明過程：根據(jù)定義5-2（正則代換），定義5-3（正則表達式）及定義4-1（正則表達式），利用數(shù)學(xué)歸納法。定理5-4（續(xù)）設(shè)L是∑上的一個

RL

是正則代換，則f(L)也是

RL。證明：描述工具：RE。對r中運算符的個數(shù)n施以歸納，證明f(r)是表示f(L)的RE。定理5-4（續(xù)）當n=0時，結(jié)論成立。當n≤k時定理成立,即當r中運算符的個數(shù)不大于k時：f(L(r))=L(f(r))。當n=k+1時，定理5-4（續(xù)）⑴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))定理5-4（續(xù)）⑵r=r1r2。

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))定理5-4（續(xù)）⑶r=r1*。

f(L)=f(L(r))=f(L(r1*))=f(L(r1)*) RE的定義

=(f(L(r1)))*

正則代換的定義

=(L(f(r1)))*

歸納假設(shè)

=L(f(r1)*) RE的定義

=L(f(r1*)) RE的正則代換的定義

=L(f(r))例5-4設(shè)

={0,1},={a,b},f(0)=a,f(1)=b*，(注意沒有嚴格區(qū)分a與{a},b*本身是一個正則表達式，它表示了一個集合)則f(L(0*(0+1)1*)=L(a*(a+b*)b*)

=L(a*ab*+a*b*b*)=L(a*b*)例5-5設(shè)

={0,1,2},={a,b},f(0)=ab,f(1)=b*a*,f(2)=a*(a+b)，則f(010)=abb*a*ab=ab+a+b

f((0+1+2)*)

=

(ab+b*a*+a*(a+b))*=

(ab+b*a*+a++a*b)*f(0(0+1+2)*)

=ab(a+b)*f(012)

=abb*a*a*(a+b)

=ab+a*(a+b)定義5-4設(shè),

是兩個字母表，f:

*為映射。如果對于x,y*，f(xy)=f(x)f(y)則稱f

為從到*的同態(tài)映射(homomorhism)。對于L

*，L的同態(tài)像f(L)=f(x)定義5-4(續(xù))對于w

*，w的同態(tài)原像是一個集合f-1(w)={x|f(x)=w且x*}對于L

*，L的同態(tài)原像是一個集合f-1(L)={x|f(x)L}例5-6設(shè)

={0,1},={a,b},f(0)=aa,f(1)=aba,則f(01)=aaaba

f((01)*)=(aaaba)*f-1(aab)=?f-1({aaa,aba,abaaaaa,abaaaaaa})={1,100}f-1((ab+ba)*a)={1}f(f-1((ab+ba)*a))={aba}f(f-1(L))=L？？？？注意同態(tài)映射是正則代換的特例原因：比較其值域可知正則代換的值域為2*同態(tài)映射的值域為*推論5-1RL的同態(tài)像是RL。證明：注意到同態(tài)映射是正則代換的特例，可以直接得到此結(jié)論。此推論表明，

RL在同態(tài)映射下是封閉的。定理5-5RL的同態(tài)原像是RL。構(gòu)造，證明(略)。定義5-5設(shè)L1,L2

*，L2除以L1的商（quotient）定義為L1/L2

={x|yL2st.xyL1}對商的計算：考慮句子的后綴例5-7考慮

{0,1}上的如下語言設(shè)L1=01,L2=01,

則L1/L2={}設(shè)L1=(01)*,L2=(01)*,則L1/L2=L1設(shè)L1=0*011*,L2=00,則L1/L2=?設(shè)L1=00*1*1,L2=00*1*1,則L1/L2=0*練習(xí)設(shè)L1={000},L2={},

L3={，0},L4={，0,00},L5={，0,00,000},則L1/L2=L1/L3=L1/L4=L1/L5={000}，{000，00}，{000，00,0}，

{000，00,0，}定理5-6

設(shè)L1、L2∑*，如果L1是

RL，則L1/L2也是

RL。證明：設(shè)L1

∑*是

RL，

DFAM=(Q，∑，δ，q0，F(xiàn))，L(M)=L1DFAM′=(Q，∑，δ，q0，F(xiàn)′)F′={q|y∈L2，δ(q，y)∈F}顯然，

L(M′)=L1/L2。定理得證。

定理5-6（續(xù)）注意L2可以是任意語言，所以這種封閉性不是有效封閉性。5.3Myhill-Nerode定理與DFA的極小化2023/2/3515.3.1Myhill-Nerode定理定義5-6DFAM確定的等價關(guān)系。

M=(Q，∑，δ，q0，F(xiàn))，對于x，y∈∑*xRMyδ(q0，x)=δ(q0，y)。顯然，xRMy

q∈Q，x，y∈set(q)

2023/2/3525.3.1Myhill-Nerode定理例5-8設(shè)

L=0*10*，它對應(yīng)的DFAM如下圖。2023/2/3535.3.1Myhill-Nerode定理對應(yīng)于q0：(00)nRM(00)m n，m≥0；對應(yīng)于q1：0(00)nRM0(00)m n，m≥0；對應(yīng)于q2：(00)n1

RM(00)m1 n，m≥0；對應(yīng)于q3：0(00)n1RM0(00)m1 n，m≥0；對應(yīng)于q4：0(00)n10kRM0(00)m10h

n，m≥0,k,h≥1；

(00)n10kRM(00)m10h n,m≥0，k,h≥1；

0(00)n10kRM(00)m10h n,m≥0，k,h≥1；也就是：

0n10kRM0m10h n,m≥0，k,h≥1；對應(yīng)于q5：xRMy——x，y為至少含兩個1的串。

2023/2/3545.3.1Myhill-Nerode定理定義5-7L確定的∑*上的關(guān)系RL。

對于x，y∈∑*，

xRLy(對z∈∑*，xz∈Lyz∈L)

對于x，y∈∑*，如果xRLy，則在x和y后無論接∑*中的任何串z，xz和yz要么都是L的句子，要么都不是L的句子。

2023/2/3555.3.1Myhill-Nerode定理任意x，y∈set(q)，δ(q0，x)=δ(q0，y)=q對于z∈∑*，δ(q0，xz)=δ(δ(q0，x)，z))=δ(q，z)=δ(δ(q0，y)，z)=δ(q0，yz)這就是說，δ(q0，xz)∈Fδ(q0，yz)∈F2023/2/3565.3.1Myhill-Nerode定理即，對于z∈∑*，

xz∈Lyz∈L。表明，

xRLy，也就是xRL(M)y。2023/2/3575.3.1Myhill-Nerode定理定義5-8右不變的(rightlnvariant)等價關(guān)系

設(shè)R是∑*上的等價關(guān)系，對于x，y∈∑*，如果xRLy，則必有xzRLyz，對于z∈∑*成立，則稱R是右不變的等價關(guān)系。2023/2/3585.3.1Myhill-Nerode定理命題5-1

對任意DFAM=(Q，∑，δ，q0，F(xiàn))，M確定的∑*上的關(guān)系RM為右不變的等價關(guān)系證明：⑴RM是等價關(guān)系。自反性顯然。對稱性：x，y∈∑*，xRMyδ(q0，x)=δ(q0，y) 根據(jù)RM的定義；δ(q0，y)=δ(q0，x) “=”的對稱性；

yRMx 根據(jù)RM的定義。

2023/2/3595.3.1Myhill-Nerode定理傳遞性：設(shè)xRMy，yRMz。由于xRMy，δ(q0，x)=δ(q0，y)由于yRMz，

δ(q0，y)=δ(q0，z)由“=”的傳遞性知，

δ(q0，x)=δ(q0，z)再由RM的定義得：

xRMz即RM是等價關(guān)系。

2023/2/3605.3.1Myhill-Nerode定理⑵RM

是右不變的設(shè)xRMy。則δ(q0，x)=δ(q0，y)=q所以，對于z∈∑*，δ(q0，xz)=δ(δ(q0，x)，z))=δ(q，z)=δ(δ(q0，y)，z)=δ(q0，yz)這就是說，δ(q0，xz)=δ(q0，yz)，再由RM的定義，

xzRMyz所以，RM

是右不變的等價關(guān)系。

2023/2/3615.3.1Myhill-Nerode定理命題5-2

對于任意L∑*，L所確定的∑*上的關(guān)系RL為右不變的等價關(guān)系。證明：⑴RL是等價關(guān)系。

自反性顯然。對稱性：不難看出：xRLy(對z∈∑*，xz∈Lyz∈L)yRLx

2023/2/3625.3.1Myhill-Nerode定理傳遞性：設(shè)xRLy，yRLz。

xRLy(對w∈∑*，xw∈Lyw∈L) yRLz(對w∈∑*，yw∈Lzw∈L)所以，

(w∈∑*,xw∈Lyw∈L 且yw∈Lzw∈L)即：

(對w∈∑*，xw∈Lzw∈L)故：

xRLz即RL是等價關(guān)系。

2023/2/3635.3.1Myhill-Nerode定理⑵RL

是右不變的。

設(shè)xRLy。由RL的定義，對w，v∈∑*，xwv∈Lywv∈L，注意到v的任意性，知，xwRLyw。所以，RL是右不變的等價關(guān)系。

2023/2/3645.3.1Myhill-Nerode定理定義5-9指數(shù)(index)設(shè)R是∑*上的等價關(guān)系，則稱|∑*/R|是R關(guān)于∑*的指數(shù)。簡稱為R的指數(shù)。簡稱∑*的關(guān)于R的一個等價類，也就是∑*/R的任意一個元素，為R的一個等價類

2023/2/3655.3.1Myhill-Nerode定理例5-9

圖5-4所給DFAM所確定的RM的指數(shù)為6。RM將∑*分成6個等價類：

set(q0)={(00)n|n≥0}；

set(q1)={0(00)n|n≥0}；

set(q2)={(00)n1

|

n，m≥0}；

set(q3)={0(00)n1|n≥0}；

set(q4)={0n10k|n≥0，k≥1}；

set(q5)={x|x為至少含兩個1的串}。2023/2/3665.3.1Myhill-Nerode定理RM是RL(M)的“加細”(refinement)x，y∈∑*，如果xRMy，必有xRL(M)y成立。即對于任意DFAM=(Q,∑,δ,q0,F)。

|∑*/RL(M)|≤|∑*/RM|≤|Q|按照RM中被分在同一等價類的串，在按照RL(M)分類時，一定會被分在同一個等價類。RM對∑*的劃分比RL(M)對∑*的劃分更“細”。稱RM是RL(M)的“加細”(refinement)。

2023/2/3675.3.1Myhill-Nerode定理∑*/RM={set(q0)，set(q1)，set(q2)，set(q3)，set(q4)，set(q5)}⑴取00∈set(q0)，000∈set(q1)。對于任意的x∈∑*，當x含且只含一個1時，00x∈L(M)，000x∈L(M)；當x不含1或者含多個1時，00xL(M)，000xL(M)。這就是說，對于任意的x∈∑*，00x∈L(M)000x∈L(M)。即按照RL(M)，00與000被分在同一個等價類中。從而set(q0)和set(q1)被包含在RL(M)的同一個等價類中。

2023/2/3685.3.1Myhill-Nerode定理⑵取00∈set(q0)，001∈set(q2)。取特殊的字符串1∈∑*，001∈L(M)，但0011L(M)。所以，根據(jù)RL(M)，set(q0)和set(q2)不能被“合并”到一個等價類中。類似地，根據(jù)RL(M)，set(q3)、set(q4)、set(q5)也都不能被“合并”到set(q0)的句子所在的等價類中。

2023/2/3695.3.1Myhill-Nerode定理⑶取001∈set(q2)，01∈set(q3)。對于任意的x∈∑*，x要么不含1，要么含有1。當x不含1時，001x∈L(M)，01x∈L(M)；

當x含有1時，001xL(M)，01xL(M)。這就是說，對于任意的x∈∑*，001x∈L(M)01x∈L(M)。即按照RL(M)，001與01屬于RL(M)的同一個等價類中。從而set(q2)和set(q3)被包含在RL(M)的同一個等價類中。

2023/2/3705.3.1Myhill-Nerode定理⑷取1∈set(q2)，

10∈set(q4)。對于任意的x∈∑*，x要么不含1，要么含有1。當x不含1時，1x∈L(M)，10x∈L(M)；當x含有1時，1xL(M)，10xL(M)。這就是說，對于任意的x∈∑*，1x∈L(M)10x∈L(M)。即按照RL(M)，1與10被分在RL(M)的同一個等價類中。從而在set(q2)和set(q4)被包含在RL(M)的同一個等價類中。

2023/2/3715.3.1Myhill-Nerode定理⑸取1∈set(q2)，

11∈set(q5)。注意1ε=1，11ε=11；而1∈L(M)，11L(M)。即1和11不滿足關(guān)系RL(M)，所以，set(q2)和set(q5)不能被“合并”到RL(M)的同一個等價類中。在這里，ε∈∑*是一個特殊的字符串。2023/2/3725.3.1Myhill-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*10*1(0+1)*。

2023/2/3735.3.1Myhill-Nerode定理定理5-7(Myhill-Nerode定理)如下三個命題等價：

⑴

L∑*是

RL；⑵

L是∑*上的某一個具有有窮指數(shù)的右不變等價關(guān)系R的某些等價類的并；⑶

RL具有有窮指數(shù)。2023/2/3745.3.1Myhill-Nerode定理證明：

由(1)可以推出(2)設(shè)L∑*是

RL，所以，存在DFAM=(Q，∑，δ，q0，F(xiàn))，使得L(M)=L。由命題5-1，RM是∑*上的右不變等價關(guān)系，而且|∑*/RM|≤|Q|，所以，RM具有有窮指數(shù)。而

L是∑*上的具有有窮指數(shù)的右不變等價關(guān)系RM的、對應(yīng)于M的終止狀態(tài)的等價類的并。

2023/2/3755.3.1Myhill-Nerode定理由(2)可以推出(3)。設(shè)xRy，由R的右不變性可知，對于任意z∈∑*，xzRyz而L是R的某些等價類的并，所以，xz∈Lyz∈L根據(jù)RL的定義，xRLy故R是RL的加細。由于R具有有窮指數(shù)，所以，RL具有有窮指數(shù)。

2023/2/3765.3.1Myhill-Nerode定理由(3)可以推出(1)。令M′=(∑*/RL,∑,δ′,[ε],{[x]|x∈L})[ε]表示ε所在的等價類對應(yīng)的狀態(tài)；[x]表示x所在的等價類對應(yīng)的狀態(tài)。對于([x],a)∈(∑*/RL)×∑,δ′([x],a)=[xa]δ′定義的相容性:如果[x]=[y]，對a∈∑,有[xa]=[ya]。

L(M′)=L2023/2/3775.3.1Myhill-Nerode定理例5-10

用定理5-7證明{0n1n|n≥0}不是

RL根據(jù)L的句子的特征來尋找RL的等價類。

L的句子的主要特點有兩個：⑴

句子中所含的字符0的個數(shù)與所含的字符1的個數(shù)相同。⑵

所有的0都在所有的1的前面可以得到如下一些等價類。2023/2/3785.3.1Myhill-Nerode定理[10]={x|x=0n1m(m≥n+1)或者x中含子串10}[ε]——ε所在的等價類；[1]——0所在的等價類；[2]——00所在的等價類；[3]——000所在的等價類；…[n]——0n所在的等價類；…所以，RL的指數(shù)是無窮的。因此，L不是

RL。2023/2/3795.3.1Myhill-Nerode定理推論5-1

對于任意的

RLL，如DFAM=(Q，∑，δ，q0，F(xiàn))滿足L(M)=L，則|∑*/RL|≤|Q|。表明對任意一個

RLL，按照定理中所給的方法構(gòu)造出來的DFAM′是一個接受L的最小DFA。這個DFA是唯一的么？

2023/2/3805.3.1Myhill-Nerode定理推論5-2

對于任意的

RLL，同構(gòu)意義下，接受L的最小DFA是唯一的。作業(yè)7(1)(3)(8)2023/2/3825.3.2DFA的極小化定義5-10可以區(qū)分的(distinguishable)狀態(tài)設(shè)DFAM=(Q，∑，δ，q0，F(xiàn))，如果x∈∑*，

對Q中的兩個狀態(tài)q和p，使得δ(q，x)∈F和δ(p，x)∈F中，有且僅有一個成立，則稱p和q是可以區(qū)分的。否則，稱q和p等價。并記作q≡p

。2023/2/3835.3.2DFA的極小化算法5-1DFA的極小化算法算法思想：掃描所有的狀態(tài)對，找出所有的可區(qū)分的狀態(tài)對，不可取分的狀態(tài)對一定是等價的。輸入：給定的DFA。輸出：可區(qū)分狀態(tài)表。主要數(shù)據(jù)結(jié)構(gòu)：狀態(tài)對的關(guān)聯(lián)鏈表；可區(qū)分狀態(tài)表。

2023/2/3845.3.2DFA的極小化主要步驟⑴for

(q，p)∈F×(Q-F)do

標記可區(qū)分狀態(tài)表中的表項(q，p)；⑵for(q,p)∈F×F∪(Q-F)×(Q-F)&q≠pdo⑶ if

a∈∑，可區(qū)分狀態(tài)表中的表項(δ(q，a)，δ(p，a))已被標記

then begin⑷ 標記可區(qū)分狀態(tài)表中的表項(q，p)；⑸ 遞歸地標記本次被標記的狀態(tài)對的關(guān)聯(lián)鏈表上的各個狀態(tài)對在可區(qū)分狀態(tài)表中的對應(yīng)表項

end

2023/2/3855.3.2DFA的極小化⑹ elsefor

a∈∑，do⑺ ifδ(q，a)≠δ(p，a)&(q，