資源描述：
《上下文無關(guān)語(yǔ)言和非上下文無關(guān)語(yǔ)言》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、語(yǔ)言與計(jì)算理論導(dǎo)引上下文無關(guān)語(yǔ)言與非上下文無關(guān)語(yǔ)言8上下文無關(guān)語(yǔ)言和非上下文無關(guān)語(yǔ)言8.1上下文無關(guān)語(yǔ)言的泵引理從第6章到第7章，我們給出了兩種描述CFL的模型，CFG和PDA。這兩種模型都沒有提供直接、明確的方法來判斷一個(gè)形式語(yǔ)言不是CFL。然而，正如例子6.7對(duì)自然語(yǔ)言的一個(gè)簡(jiǎn)單考察，我們發(fā)現(xiàn)CFG存在描述能力的局限。本節(jié)中，我們精確定義和討論CFL的一個(gè)性質(zhì)，它類似于正則語(yǔ)言的泵引理。利用這個(gè)性質(zhì)能夠發(fā)現(xiàn)許多不是CFL的語(yǔ)言。正則語(yǔ)言的泵引理基于這樣的事實(shí)，如果一個(gè)足夠長(zhǎng)的輸入字符串x導(dǎo)致FA在
2、狀態(tài)轉(zhuǎn)移中，到達(dá)某個(gè)狀態(tài)超過一次，即接受路徑上存在回路，根據(jù)回路容易將x分成三部分，u是回路之前的字符串，v是回路的字符串，w是回路后的字符串，那么在回路上的多次重復(fù)，得到的新的字符串也應(yīng)該被FA接受，即對(duì)任意的m>=0，uvmw被FA接受。如果我們用CFG生成（而不是PDA移動(dòng)）CFL，容易得到類似的觀察。設(shè)CFGG的一個(gè)推導(dǎo)出現(xiàn)同一個(gè)非終結(jié)符的嵌套重復(fù)，如下面的形式，ST*vAzT*vwAyzT*vwxyz其中，v,w,x,y,z??*。推導(dǎo)過程中，出現(xiàn)了AT*wAy，我們可以多次重復(fù)這個(gè)推導(dǎo)過程
3、，如ST*vAzT*vwAyzT*vw2Ay2zT*vw3Ay3zT*...T*vwmAymz又由于AT*x，因此所有這類字符串vxz,vwxyz,vw2xy2z,...,vwmxymz都輸入語(yǔ)言L(G)。為了將上面的觀察總結(jié)成CFL的泵引理，我們必須說明對(duì)于足夠長(zhǎng)的字符串的推導(dǎo)過程中都會(huì)出現(xiàn)非終結(jié)符的嵌套重復(fù)。同時(shí)我們也盡量發(fā)現(xiàn)分解得到的5個(gè)子串：v,w,x,y,z，的一些性質(zhì)。這類似于我們處理正則語(yǔ)言的泵引理。在6.6節(jié)，我們證明了所有的CFG產(chǎn)生式都可以改寫成Chomsky范式，而不會(huì)影響CFG
4、接受語(yǔ)言的能力（唯一的影響是不能接受空字符，由于此處僅僅關(guān)心足夠長(zhǎng)的字符串，因此這個(gè)影響可以忽略）。因此我們的討論可以局限在Chomsky范式（CNF）表示的CFG，顯然這類文法得到的推導(dǎo)樹都是二叉樹，即每個(gè)父節(jié)點(diǎn)至多有兩個(gè)子節(jié)點(diǎn)。我們先定義幾個(gè)與二叉樹相關(guān)的概念。路徑是一串節(jié)點(diǎn)組成的序列，前后節(jié)點(diǎn)之間有父子關(guān)系；路徑的長(zhǎng)度是路徑包含的節(jié)點(diǎn)的個(gè)數(shù)；二叉樹的高度是最長(zhǎng)路徑的長(zhǎng)度。由于非終結(jié)符數(shù)目有限，如果推導(dǎo)樹足夠高，那么存在一個(gè)路徑，某個(gè)非終結(jié)符在該路徑上出現(xiàn)了兩次，即出現(xiàn)了前面提到的嵌套重復(fù)現(xiàn)象。引
5、理8.1任給h>=1，如果二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)>2h-1，那么該二叉樹的高度>h。證明：這是一個(gè)數(shù)學(xué)問題。我們用數(shù)學(xué)歸納法證明它的逆反命題：如果二叉樹的高度<=h，那么二叉樹的葉節(jié)點(diǎn)個(gè)數(shù)<=2h-1。1.歸納基礎(chǔ)，h=1，此時(shí)二叉樹只有一個(gè)根節(jié)點(diǎn)，它也是唯一的葉結(jié)點(diǎn)，命題成立。2.歸納推理，設(shè)k>=1時(shí)，命題成立。要證明k+1時(shí)，命題也成立。設(shè)二叉樹T的高度為k+1，則它的根節(jié)點(diǎn)的兩個(gè)子樹（以子節(jié)點(diǎn)為跟的二叉樹）的葉節(jié)點(diǎn)數(shù)都<=2k-1，因此T的葉節(jié)點(diǎn)數(shù)<=2k-1+2k-1=2k。得證。定理8.1G=
6、(V,?,S,P)是形式為CNF的CFG，共有p個(gè)非終結(jié)符，則對(duì)每個(gè)長(zhǎng)度>=2p+1的屬于L(G)的字符串，都能找到5個(gè)字符串v,w,x,y,z滿足下面的條件：u=vwxyz
7、wy
8、>0
9、wxy
10、<=2p+1vwmxymz?L(G),"m>=0證明：根據(jù)引理8.1，任何一個(gè)生成u的推導(dǎo)樹高度>=p+2，即至少存在一個(gè)長(zhǎng)度>=p+2的路徑，不妨設(shè)d是其中的一個(gè)，顯然d10陶曉鵬Copyright2003語(yǔ)言與計(jì)算理論導(dǎo)引上下文無關(guān)語(yǔ)言與非上下文無關(guān)語(yǔ)言的最底部是一個(gè)終結(jié)符，其上的符號(hào)都是非終結(jié)符，共有p
11、+1個(gè)，而不同的非終結(jié)符只有p個(gè)，根據(jù)鴿籠法則，至少存在一個(gè)非終結(jié)符A在路徑d上出現(xiàn)了至少兩次，分別將其中最接近根和最接近葉的標(biāo)記為A1和A2，設(shè)A2生成的字符串是x，A1生成的字符串是wxy。在wxy之前的字符串記為v，在wxy之后的字符串記為z。圖8-1直觀地給出了這5個(gè)字符串在推導(dǎo)樹上的位置。由于A1為根的推導(dǎo)樹高度<=p+2，因此
12、wxy
13、<=2p+1。由于A1為根的推導(dǎo)樹是二叉樹，因此出了存在從A1到A2的路徑，還存在其他路徑，則
14、wy
15、>0。最后，存在如下的嵌套重復(fù)，ST*vAzT*vwA
16、yzT*vwxyz因此滿足第4個(gè)條件。類似有限自動(dòng)機(jī)的泵引理，我們也給出一系列CFG的泵引理。定理8.1a（CFL的泵引理）語(yǔ)言L是CFL，則存在一個(gè)整數(shù)n，使得對(duì)每個(gè)u?L，
17、u
18、>=n，都存在5個(gè)字符串v,w,x,y,z，滿足下面的條件，u=vwxyz(8.1)
19、wy
20、>0(8.2)
21、wxy
22、<=n(8.3)vwmxymz?L(G),"m>=0(8.4)證明：L是CFL，則存在一個(gè)CNF形式的CFG生成L-{L}，它的非終結(jié)符個(gè)數(shù)是p，則令n=2p+
