自動(dòng)機(jī)與形式語(yǔ)言-第五章-泵引理

2023/2/51第五章

正則語(yǔ)言的性質(zhì)2023/2/52正則語(yǔ)言的描述RGDFANFAε-NFARERegularLanguage2023/2/53語(yǔ)言的性質(zhì)語(yǔ)言的兩種重要性質(zhì)判定性質(zhì)(DecisionProperties)封閉性質(zhì)(ClosureProperties)RL性質(zhì)判定性質(zhì)：泵引理及其應(yīng)用封閉性質(zhì)：并、乘積、閉包、補(bǔ)、交、正則代換、同態(tài)、逆同態(tài)的封閉性

DFA的極小化

2023/2/54判定性質(zhì)DecisionProperties語(yǔ)言的判定性質(zhì)：以語(yǔ)言的形式化描述(例如：DFA)作為輸入，判定某些性質(zhì)是否成立的算法。例子：DFA對(duì)應(yīng)的語(yǔ)言L是否為空？2023/2/55判定性質(zhì)DecisionProperties其他判定性質(zhì)：成員關(guān)系：“w是否在正則語(yǔ)言L里？”空否：“DFA對(duì)應(yīng)語(yǔ)言是否為空？”有窮否：“DFA對(duì)應(yīng)語(yǔ)言是否有窮？”“語(yǔ)言L是否為正則語(yǔ)言？”→泵引理兩個(gè)DFA等價(jià)否：“兩個(gè)DFA對(duì)應(yīng)語(yǔ)言是否等價(jià)？”2023/2/56判定性質(zhì)DecisionProperties為什么要討論語(yǔ)言的判定性質(zhì)？例子：當(dāng)我們用DFA來(lái)描述協(xié)議(protocol)，該協(xié)議的重要性質(zhì)跟DFA對(duì)應(yīng)的語(yǔ)言相關(guān)。如：“該協(xié)議是否會(huì)終結(jié)？”=“該語(yǔ)言是否是有窮的？”“該協(xié)議是否會(huì)失效？”=“該語(yǔ)言是否為非空的？”2023/2/57判定性質(zhì)DecisionProperties為什么要討論語(yǔ)言的判定性質(zhì)？例子：我們經(jīng)常想要一個(gè)“極小的”語(yǔ)言表示，比如一個(gè)擁有最少狀態(tài)數(shù)量的DFA或者一個(gè)最短的RE如果我們不能判定“兩個(gè)語(yǔ)言是否等價(jià)？”或者，“兩個(gè)DFA是否對(duì)應(yīng)相同的語(yǔ)言？”我們就無(wú)法找到“極小”2023/2/58成員判定MembershipQuestion第一個(gè)判定性質(zhì)的問(wèn)題：“字符串w是否在正則語(yǔ)言L里面？”假定L用DFAM來(lái)描述模擬字符串w輸入時(shí)，M的狀態(tài)轉(zhuǎn)移Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate92023/2/5Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate102023/2/5Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate112023/2/5Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate122023/2/5Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate132023/2/5Example:TestingMembershipStart10ACB100,101011NextsymbolCurrentstate142023/2/52023/2/515成員判定MembershipQuestion如果正則語(yǔ)言RL不是用DFA來(lái)描述的怎么辦？RGDFANFAε-NFARE定理5-13

設(shè)L是字母表∑上的

RL，對(duì)任意x∈∑*，存在判定x是不是L的句子的算法。從一定的意義上講，接受L的DFAM就是判定x是否L的一個(gè)句子的“算法”。

2023/2/516成員判定MembershipQuestion2023/2/517空否判定EmptinessQuestion給定一個(gè)正則語(yǔ)言L,問(wèn)：該語(yǔ)言是否包含任何字符串？即L是否為空？假定語(yǔ)言描述為DFA：構(gòu)建狀態(tài)轉(zhuǎn)移圖；計(jì)算從開(kāi)始狀態(tài)q0出發(fā)，所有可達(dá)到狀態(tài)的集合；若任何接受狀態(tài)是可到達(dá)的，則該語(yǔ)言非空，否則該語(yǔ)言為空。2023/2/518空否判定EmptinessQuestion給定一個(gè)正則語(yǔ)言L,問(wèn)：該語(yǔ)言是否包含任何字符串？即L是否為空？判斷下列DFA對(duì)應(yīng)語(yǔ)言是否為空：定理5-10

設(shè)DFAM=(Q，∑，δ，q0，F(xiàn))，L=L(M)非空的充分必要條件是：存在x∈∑*，|x|<|Q|，δ(q0，x)∈F。

證明：充分性顯然。必要性：M的狀態(tài)轉(zhuǎn)移圖中必存在一條從q0到某一個(gè)終止?fàn)顟B(tài)qf且無(wú)重復(fù)狀態(tài)的路，此路中的狀態(tài)數(shù)n≤|Q|。此路的標(biāo)記x滿足|x|≤n-1。而δ(q0，x)∈F。即x是L=L(M)的長(zhǎng)度小于|Q|的句子。

2023/2/519空否判定EmptinessQuestion2023/2/520無(wú)窮判定InfinitenessQuestion給定一個(gè)正則語(yǔ)言L,問(wèn)：該語(yǔ)言是否無(wú)窮？給定L對(duì)應(yīng)的DFA：若該DFA有n個(gè)狀態(tài),

L包含長(zhǎng)度大于等于n的字符串，則該語(yǔ)言無(wú)窮。否則，該語(yǔ)言L一定是有窮的。有窮無(wú)窮2023/2/521無(wú)窮判定InfinitenessQuestion證明：若該DFA有n個(gè)狀態(tài),

L包含長(zhǎng)度大于等于n的字符串，則該語(yǔ)言無(wú)窮。如果一個(gè)DFA有n個(gè)狀態(tài)，并接受長(zhǎng)度大于等于n的字符串w，那么在w的路徑上，一定包含一個(gè)狀態(tài)出現(xiàn)了至少兩次。原因：長(zhǎng)度大于等于n的字符串w的路徑上經(jīng)過(guò)的狀態(tài)數(shù)量至少為n+122w=xyzxyzThenxyizisinthelanguageforalli>0.Sinceyisnotε,weseeaninfinitenumberofstringsinL.無(wú)窮判定InfinitenessQuestion2023/2/523無(wú)窮判定InfinitenessQuestion我們尚無(wú)一個(gè)有效算法有無(wú)窮個(gè)字符串長(zhǎng)度大于等于n，我們無(wú)法窮舉測(cè)試Second

idea：如果L包含長(zhǎng)度大于等于n的字符串，那么一定包含長(zhǎng)度介于n跟2n-1的句子。2023/2/524無(wú)窮判定InfinitenessQuestion證明：如果L包含長(zhǎng)度大于等于n的字符串，那么一定包含長(zhǎng)度介于n跟2n-1的句子。w=xyz，y為路徑上的第一個(gè)環(huán)那么：x<n;1<

|y|<n；z<n

|xz|<2n若|xz|≥n，則為所求否則|xz|<n，增加句子xyiz長(zhǎng)度至[n,2n-1]xyz2023/2/525無(wú)窮判定InfinitenessQuestion算法：檢驗(yàn)所有長(zhǎng)度[n,2n-1]的句子，如果有句子被接受，則該語(yǔ)言無(wú)窮。糟糕的算法改進(jìn)：從開(kāi)始狀態(tài)到接受狀態(tài)找環(huán)xyz26在無(wú)窮判定中,我們無(wú)意中提供了一個(gè)證明一個(gè)語(yǔ)言是否正則語(yǔ)言的重要結(jié)論。Calledthepumpinglemmaforregularlanguages

(泵引理).泵引理The

Pumping

Lemma5.1RL的泵引理泵引理(pumpinglemma)

設(shè)L為一個(gè)RL，則存在僅依賴于L的正整數(shù)N，對(duì)于z∈L，如果|z|≥N，則存在u、v、w，滿足⑴z=uvw；⑵|uv|≤N；⑶|v|≥1；⑷對(duì)于任意的整數(shù)i≥0，uviw∈L；⑸N不大于接受L的最小DFAM的狀態(tài)數(shù)。

2023/2/5275.1RL的泵引理證明思想2023/2/5285.1RL的泵引理證明：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)成的非空子串可以重復(fù)任意多次。2023/2/529M=(Q，∑，δ，q0，F(xiàn))

|Q|=N

z=a1a2…am m≥N

δ(q0，a1a2…ah)=qh

狀態(tài)序列q0，q1，…，qN中，至少有兩個(gè)狀態(tài)是相同：qk=qj

2023/2/5305.1RL的泵引理δ(q0，a1a2…ak)=qkδ(qk，ak+1…aj)=qj=qkδ(qj，aj+1…am)=qm對(duì)于任意的整數(shù)i≥0

δ(qk，(ak+1…aj)i)=δ(qk，(ak+1…aj)i-1)…=δ(qk，ak+1…aj)=qk

2023/2/5315.1RL的泵引理故，δ(q0，a1a2…ak(ak+1…aj)iaj+1…am)=qm也就是說(shuō)，a1a2…ak(ak+1…aj)iaj+1…am∈L(M)u=a1a2…ak，v=ak+1…aj，w=aj+1…am

uviw∈L

2023/2/5325.1RL的泵引理例5-1

證明{0n1n|n≥1}不是RL。證明：

假設(shè)L={0n1n|n≥1}是RLz=0N1N

按照泵引理所述

v=0k k≥1

此時(shí)有，

u=0N-k-j w=0j1N

2023/2/5335.1RL的泵引理從而有，

uviw=0N-k-j(0k)i0j1N=0N+(i-1)k1N

當(dāng)i=2時(shí)，我們有：

uv2w=0N+(2-1)k1N=0N+k1N注意到k≥1，所以，N+k>N。這就是說(shuō)，0N+k1NL這與泵引理矛盾。所以，L不是RL。2023/2/5345.1RL的泵引理例5-2證明{0n|n為素?cái)?shù)}不是RL。

證明：假設(shè)L={0n|n為素?cái)?shù)}是RL。取z=0N+p∈L，不妨設(shè)v=0k， k≥1從而有，

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

=0N+p+(i-1)k2023/2/5355.1RL的泵引理當(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)注意到k≥1，所以

N+p+(N+p+1-1)k=(N+p)(1+k)不是素?cái)?shù)。故當(dāng)i=N+p+1時(shí)，uvN+p+1w=0(N+p)(1+k)

L這與泵引理矛盾。所以，L不是RL。

2023/2/5365.1RL的泵引理例5-3

證明{0n1m2n+m|m，n≥1}不是RL。

證明：假設(shè)L={0n1m2n+m|m，n≥1}是RL。取z=0N1N22N

設(shè) v=0k k≥1

從而有，

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

=0N+(i-1)k1N22N2023/2/5375.1RL的泵引理 uv0w=0N+(0-1)k1N22N

=0N-k1N22N

注意到k≥1，N-k+N=2N-k<2N0N-k1N22N

L這個(gè)結(jié)論與泵引理矛盾。所以，L不是RL。

2023/2/5385.1RL的泵引理用來(lái)證明一個(gè)語(yǔ)言不是RL不能用泵引理去證明一個(gè)語(yǔ)言是RL。

⑴由于泵引理給出的是RL的必要條件，所以，在用它證明一個(gè)語(yǔ)言不是RL時(shí)，我們使用反證法。

⑵泵引理說(shuō)的是對(duì)RL都成立的條件，而我們是要用它證明給定語(yǔ)言不是RL，這就是說(shuō)，相應(yīng)語(yǔ)言的“僅僅依賴于L的正整數(shù)N”實(shí)際上是不存在的。所以，我們一定是無(wú)法給出一個(gè)具體的數(shù)的。因此，人們往往就用符號(hào)N來(lái)表示這個(gè)“假定存在”、而實(shí)際并不存在的數(shù)。

2023/2/5395.1RL的泵引理⑶由于泵引理指出，如果L是RL，則對(duì)任意的z∈L，只要|z|≥N，一定會(huì)存在u、v、w，使uviw∈L對(duì)所有的i成立。因此，我們?cè)谶x擇z時(shí)，就需要注意到論證時(shí)的簡(jiǎn)潔和方便。

⑷當(dāng)一個(gè)特意被選來(lái)用作“發(fā)現(xiàn)矛盾”的z確定以后，就必須依照|uv|≤N和|v|≥1的要求，說(shuō)明v不存在(對(duì)“存在u、v、w”的否定)

。2023/2/5405.1RL的泵引理⑸與選z時(shí)類似，在尋找i時(shí)，我們也僅需要找到一個(gè)表明矛盾的“具體”值就可以了(對(duì)“所有i”的否定)。⑹一般地，在證明一個(gè)語(yǔ)言不是RL的時(shí)候，我們并不使用泵引理的第(5)條。⑺事實(shí)上，引理所要求的|uv|≤N并不是必須的。這個(gè)限制為我們簡(jiǎn)化相應(yīng)的證明提供了良好支撐——擴(kuò)