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

研究動機{0n1n|n

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

正則語言的性質RL性質泵引理及其應用

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

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

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

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

am

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

qm，根據鴿籠原理，則當m大于M的可達狀態(tài)數時，這些狀態(tài)至少有一對是重復的，不妨令為qk和qj，顯然kj。泵引理推導示意圖Sa1q0q1qka2…akak+1…ajqjaj+1…amqmSa1q0q1qk=qja2…akak+1…ajaj+1…amqm泵引理證明設L是一個RL，DFAM=(Q,,,q0,F)滿足L(M)=L，|Q|=N，并假設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所以對于非負整數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有：對非負整數i,uviwL注意到j

N,k<j,有：|uv|

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

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

z

=

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

|v|1，因此v只可能是由0組成的非空串設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為素數}不是RL。證明：假設L={0n|n為素數}是RL。取z=0N+p∈L，不妨設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)不是素數。故當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}

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

z

=

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

|v|1，因此v只可能是由0組成的非空串設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串被泵進/泵出時，應說明它不滿足0n1m2n+m，而不是0n1n22n。泵引理的注意事項用來證明一個語言不是RL不能用泵引理去證明一個語言是RL。

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

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

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

，f(a)是上的RL，則稱f為正則代換(regularsubstitution)。復習：*是指字母表上的克林閉包，即中若干個字符連接而成字符串的集合(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設

={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設,

是兩個字母表，映射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設L是上的一個RL,

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

RL

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

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

=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)) 歸納假設

=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)))*

歸納假設

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

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

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

={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設

={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設,

是兩個字母表，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設

={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)映射是正則代換的特例，可以直接得到此結論。此推論表明，

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

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

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

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

則L1/L2={}設L1=(01)*,L2=(01)*,則L1/L2=L1設L1=0*011*,L2=00,則L1/L2=?設L1=00*1*1,L2=00*1*1,則L1/L2=0*練習設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

設L1、L2∑*，如果L1是

RL，則L1/L2也是

RL。證明：設L1

∑*是

RL，

DFAM=(Q，∑，δ，q0，F)，L(M)=L1DFAM′=(Q，∑，δ，q0，F′)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確定的等價關系。

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

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

2023/2/3525.3.1Myhill-Nerode定理例5-8設

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

RM(00)m1 n，m≥0；對應于q3：0(00)n1RM0(00)m1 n，m≥0；對應于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；對應于q5：xRMy——x，y為至少含兩個1的串。

2023/2/3545.3.1Myhill-Nerode定理定義5-7L確定的∑*上的關系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)等價關系

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

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

yRMx 根據RM的定義。

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

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

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

xRMz即RM是等價關系。

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

是右不變的設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

是右不變的等價關系。

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

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

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

2023/2/3625.3.1Myhill-Nerode定理傳遞性：設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是等價關系。

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

是右不變的。

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

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

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

圖5-4所給DFAM所確定的RM的指數為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)。所以，根據RL(M)，set(q0)和set(q2)不能被“合并”到一個等價類中。類似地，根據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不滿足關系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是∑*上的某一個具有有窮指數的右不變等價關系R的某些等價類的并；⑶

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

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

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

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

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

2023/2/3765.3.1Myhill-Nerode定理由(3)可以推出(1)。令M′=(∑*/RL,∑,δ′,[ε],{[x]|x∈L})[ε]表示ε所在的等價類對應的狀態(tài)；[x]表示x所在的等價類對應的狀態(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根據L的句子的特征來尋找RL的等價類。

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

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

所有的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的指數是無窮的。因此，L不是

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

對于任意的

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

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

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

對于任意的

RLL，同構意義下，接受L的最小DFA是唯一的。作業(yè)7(1)(3)(8)2023/2/3825.3.2DFA的極小化定義5-10可以區(qū)分的(distinguishable)狀態(tài)設DFAM=(Q，∑，δ，q0，F)，如果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)表。主要數據結構：狀態(tài)對的關聯鏈表；可區(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)對的關聯鏈表上的各個狀態(tài)對在可區(qū)分狀態(tài)表中的對應表項

end

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

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