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