上下文無關(guān)語言和非上下文無關(guān)語言

1、語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言8 上下文無關(guān)語言和非上下文無關(guān)語言8.1上下文無關(guān)語言的泵引理從第 6 章到第7 章，我們給出了兩種描述CFL 的模型， CFG 和 PDA 。這兩種模型都沒有提供直接、明確的方法來判斷一個形式語言不是CFL 。然而，正如例子 6.7 對自然語言的一個簡單考察，我們發(fā)現(xiàn)CFG 存在描述能力的局限。本節(jié)中，我們精確定義和討論CFL 的一個性質(zhì)，它類似于正則語言的泵引理。利用這個性質(zhì)能夠發(fā)現(xiàn)許多不是CFL 的語言。正則語言的泵引理基于這樣的事實，如果一個足夠長的輸入字符串x 導(dǎo)致 FA 在狀態(tài)轉(zhuǎn)移中，到達某個狀態(tài)超過一次，即接受路徑上存在回路，根

2、據(jù)回路容易將x 分成三部分， u 是回路之前的字符串，v 是回路的字符串，w 是回路后的字符串，那么在回路上的多次重復(fù)，得到的新的字符串也應(yīng)該被FA 接受，即對任意的 m>=0 ， uvmw 被 FA 接受。如果我們用CFG 生成（而不是 PDA 移動） CFL ，容易得到類似的觀察。設(shè)CFG G 的一個推導(dǎo)出現(xiàn)同一個非終結(jié)符的嵌套重復(fù)，如下面的形式，S*vAz*vwAyz*vwxyz其中， v, w, x, y, z* 。推導(dǎo)過程中，出現(xiàn)了A*wAy ，我們可以多次重復(fù)這個推導(dǎo)過程，如S*vAz*vwAyz*vw 2Ay 2z*vw 3Ay 3z*.*vw mAy mz又由于 A*x

3、，因此所有這類字符串vxz, vwxyz, vw 2xy2z, ., vw mxy mz 都輸入語言 L(G) 。為了將上面的觀察總結(jié)成CFL 的泵引理， 我們必須說明對于足夠長的字符串的推導(dǎo)過程中都會出現(xiàn)非終結(jié)符的嵌套重復(fù)。同時我們也盡量發(fā)現(xiàn)分解得到的5 個子串： v, w, x,y, z ，的一些性質(zhì)。這類似于我們處理正則語言的泵引理。在 6.6 節(jié)，我們證明了所有的CFG 產(chǎn)生式都可以改寫成Chomsky 范式，而不會影響 CFG接受語言的能力（唯一的影響是不能接受空字符，由于此處僅僅關(guān)心足夠長的字符串，因此這個影響可以忽略）。因此我們的討論可以局限在Chomsky 范式（ CNF）表示

4、的 CFG，顯然這類文法得到的推導(dǎo)樹都是二叉樹，即每個父節(jié)點至多有兩個子節(jié)點。我們先定義幾個與二叉樹相關(guān)的概念。路徑是一串節(jié)點組成的序列，前后節(jié)點之間有父子關(guān)系；路徑的長度是路徑包含的節(jié)點的個數(shù)；二叉樹的高度是最長路徑的長度。由于非終結(jié)符數(shù)目有限，如果推導(dǎo)樹足夠高，那么存在一個路徑，某個非終結(jié)符在該路徑上出現(xiàn)了兩次，即出現(xiàn)了前面提到的嵌套重復(fù)現(xiàn)象。引理 8.1任給 h>=1 ，如果二叉樹的葉結(jié)點個數(shù)>2h-1，那么該二叉樹的高度>h。證明：這是一個數(shù)學(xué)問題。我們用數(shù)學(xué)歸納法證明它的逆反命題：如果二叉樹的高度<=h ，那么二叉樹的葉節(jié)點個數(shù)<=2 h-1。1. 歸納

5、基礎(chǔ)， h=1 ，此時二叉樹只有一個根節(jié)點，它也是唯一的葉結(jié)點，命題成立。2. 歸納推理，設(shè)k>=1 時，命題成立。要證明 k+1 時，命題也成立。設(shè)二叉樹T 的高度為k+1，則它的根節(jié)點的兩個子樹 （以子節(jié)點為跟的二叉樹） 的葉節(jié)點數(shù)都 <=2 k-1 ，因此 T的葉節(jié)點數(shù) <=2 k-1 +2k-1 =2 k。得證。定理 8.1 G=(V, S, P)是形式為 CNF 的 CFG，共有 p 個非終結(jié)符，則對每個長度>=2 p+1 的屬于 L(G) 的字符串，都能找到 5 個字符串 v, w, x, y, z 滿足下面的條件：u=vwxyz|wy|>0|wxy|

6、<=2 p+1vw mxy mz L(G),m>=0證明：根據(jù)引理8.1，任何一個生成 u 的推導(dǎo)樹高度 >=p+2 ，即至少存在一個長度>=p+2 的路徑，不妨設(shè)d 是其中的一個，顯然d 的最底部是一個終結(jié)符，其上的符號都是非終結(jié)符，共陶曉鵬Copyright 20031語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言有 p+1 個，而不同的非終結(jié)符只有p 個，根據(jù)鴿籠法則，至少存在一個非終結(jié)符A 在路徑 d 上出現(xiàn)了至少兩次， 分別將其中最接近根和最接近葉的標(biāo)記為A 1 和 A 2，設(shè) A2 生成的字符串是 x，A 1 生成的字符串是 wxy 。在 wxy 之前的

7、字符串記為v，在 wxy 之后的字符串記為z。圖 8-1 直觀地給出了這5 個字符串在推導(dǎo)樹上的位置。由于 A 1 為根的推導(dǎo)樹高度 <=p+2 ，因此 |wxy|<=2p+1 。由于 A 1 為根的推導(dǎo)樹是二叉樹，因此出了存在從A1到 A2的路徑，還存在其他路徑，則|wy|>0 。最后，存在如下的嵌套重復(fù)，S *vAz*vwAyz*vwxyz因此滿足第 4 個條件。類似有限自動機的泵引理，我們也給出一系列CFG 的泵引理。定理 8.1a（ CFL 的泵引理）語言 L 是 CFL ，則存在一個整數(shù) n，使得對每個 u L ，|u|>=n，都存在 5 個字符串 v, w,

8、 x, y, z，滿足下面的條件，u=vwxyz(8.1)|wy|>0(8.2)|wxy|<=n(8.3)vw mxy mzL(G), m>=0(8.4)證明： L 是 CFL ，則存在一個 CNF 形式的 CFG 生成 L- ，它的非終結(jié)符個數(shù)是p，則令n=2p+1 ，根據(jù)定理 8.1 直接得到定理8.1a 的結(jié)論。類似 FA 的泵引理（見第 5 章），本節(jié)的泵引理也常常用來證明某個語言不是CFL 。通常采用反證法，即要證明對任給的整數(shù)n，都存在一個 uL ，|u|>n，找不到滿足上面4 個條件的 5個字符串。還有另外的方法說明一個語言不是CFL 。根據(jù)第 7 章，由

9、一個 FA 加一個輔助存儲空間 （棧）組成的 PDA 能夠接受一個CFL ，如果我們能夠說明接受一個語言的抽象機至少需要兩個棧，那么就能說明這個語言不是CFL 。比如我們知道接受語言aibi 的抽象機只需要一個棧，即用一個棧記住前面的 a 的個數(shù)， 然后與后面的 b 比較。那么容易想到， 僅僅一個棧不能接受語言aibici。下面我們用泵引理來證明我們的直觀判斷。例子 8.1 語言 L=a ibici | i>=1 ，證明 L 不是 CFL 。分析：反證法。假設(shè)L 是 CFL ，則存在定理 8.1a 定義的 n，選擇 u=anbncn，顯然 |u|>n，設(shè)存在 5 個字符串v, w,

10、 x, y, z 滿足式子 (8.1)-(8.4) 。由于 |wxy|<=n ，因此 w, x 和 y 至多包含兩種字符，又因為 |wy|>0，因此無法滿足式子vw mxy mz L(G),m>=0 ，得到矛盾，得證。顯然這個方法實際上證明了更大的語言L 1=u a, b, c* | n a(u)=n b(u)=n c(u) 是非 CFL（選取同樣的 u）。例子 8.2 語言 L=ss | s a, b*是非 CFL 。分析：前面我們討論了語言 ssr| sa, b* 是 CFL 。例子 8.1 揭示了一個棧不夠用的情況，這個例子則顯示了數(shù)據(jù)結(jié)構(gòu)棧不合適的情況。顯然，如果PD

11、A 用到的輔助空間不是棧，而是隊列，那么就能夠類似接受回文語言那樣接受L 。反證法，設(shè) L 是 CFL ，則存在 n，選擇 u(n)=a nbnanbn，設(shè)存在 v, w, x, y, z滿足式子 (8.1)-(8.4) ，我們來發(fā)現(xiàn)其中的矛盾。 類似例子 8.1，由于 |wxy|<=n ，則 wxy 至多包含上面4 組字符串的兩組，我們分情況討論。1. wxy 包含第 1 組和第 2 組，則 vw 0xy0z=aibjanbn, i<n, j<n ，顯然 vw 0 xy0zL ，矛盾；2. wxy 包含第 2 組和第 3 組，則 vw 0xy0z=anbiajbn, i&l

12、t;n, j<n ，顯然 vw 0 xy0zL ，矛盾；3. wxy 包含第 3 組合第 4 組，則 vw 0xy0z=anbnaibj, i<n, j<n ，顯然 vw 0 xy0zL ，矛盾；其他情況可類似證明。陶曉鵬Copyright 20032語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言類似例子8.1，例子8.2 可用于證明其他一些語言不是CFL ，比如 a ibiaibi | i>=0, a i bjaibj |i,j>=0, scs | sa, b*, c是特殊字符 等。上面證明中如何選擇u 成為關(guān)鍵，盡管正確的選擇可能不止一個，但大多數(shù)選擇不能

13、導(dǎo)出矛盾。一旦 u 選好后，則往往需要分情況討論。比如例子8.2，可以分下面 7 種情況討論，1. wy 只包含第一組的 a2. wy 包含第一組的 a 和第二組的 b3. wy 只包含第二組的 b4. wy 包含第二組的 b 和第三組的 a5. wy 只包含第三組的 a6. wy 包含第三組的 a 和第四組的 b7. wy 只包含第四組的 b這些情況的討論中，常常有相似之處，可以互相借用。最后要選擇m 的值來導(dǎo)致矛盾，通常有多種值可選擇，不過用得最多的是m=0 或 m=2。例子 8.3 語言 L=xa, b, c* | n a(x)<n b(x) and n a(x)<n c(x

14、) 不是 CFL 。分析：這個例子與例子8.1 很像， PDA 只有一個棧，可以用來比較a 和 b 的數(shù)目，也可以用來比較a 和 c 的數(shù)目，但不能同時完成兩個比較，因此問題源于棧數(shù)目不夠。反證法， 設(shè) L 是 CFL ，則存在 n，令 u=anbn+1 cn+1，設(shè)存在滿足式子(8.1)-(8.4) 的 v, w, x, y, z 。分兩種情況討論：1.wy 中至少含有一個a，則 wy 不能含有c，因此 vw 2xy 2zL ；2. wy 中不含 a，則 vw 0xy0z L。兩種情況都導(dǎo)致矛盾，得證。注意，上面的方法還可用于說明語言a ibjck| i<j and i<k 不是

15、 CFL 。例子 8.4 在 5.5 節(jié)我們說明了程序設(shè)計語言C 存在不能成為正則語言的特征，在第6 章，我們用 CFG 描述了高級程序設(shè)計語言的部分語法，本例我們將說明整個高級程序設(shè)計語言，比如 C，不是 CFL 。分析： C 語言的一個特點是，變量在使用之前必須先聲明，這個規(guī)則等同于規(guī)定字符串具有這樣的形式， xcx 。其中， x 是標(biāo)識符， c 是兩個標(biāo)識符之間的字符串。例子8.2 已經(jīng)說明了語言xcx | x a, b* 不是 CFL ，本例擴大了 x 的字母表， c 變成了字符串，但問題的實質(zhì)沒有改變。反證法，設(shè)L 是 CFL ，則存在n。選擇umain() intaa.a; aa.

16、a; aa.a;nnnu 中只有一個空格在int 之后，這個句子可能帶來編譯器的警告，但能夠通過編譯器并得到可執(zhí)行程序，即先聲明了aa.a，然后兩次使用aa.a。根據(jù)泵引理，存在u=vwxyz ， |wxy|<=n ，分情況討論xy ：1. wy 包含空格，則 vw 0xy0z 不再是合法的 C 程序；2. wy 不包含空格， wxy 只在第一組 aa.a，則 vw 0xy 0z 將改變生命，后面引用非法，不是合格的 C 程序；3. 類似討論其他情況， vw 0xy0z 都不再是合法 C 程序。得到矛盾，得證。我們還可以借用例子8.2 來說明 C 程序語言不是CFL 。例子 8.2 說明

17、了 a nbmanb m | n,m>=0不是 CFL ， C 語言中函數(shù)調(diào)用可以轉(zhuǎn)換成這種形式，比如有兩個函數(shù)f 和 g，分別有 n 和 m 個參數(shù)，每次調(diào)用都遵循anbm 的形式。陶曉鵬Copyright 20033語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言類似 FA 的泵引理有多種弱形式，本節(jié)也給出CFG 的泵引理的弱形式，它應(yīng)用的范圍更廣，稱為 Ogden 引理。泵引理給出了字符串的“泵”，w 和 y，的一些信息，但沒有談及這些子串在 u 中的位置。 Ogden 引理能夠明確指示 u 中某部分包含“泵”，因此提供了比泵引理更豐富的信息，有時能夠解決泵引理無法解決的問題。定

18、理 8.2 （ Ogden 引理） L 是一個 CFL ，則存在一個整數(shù)n，使得任給 u L, |u|>=n，給 u中>=n 個字符做標(biāo)記，則存在5 個字符串 v, w, x, y, z 滿足，u=vwxyz(8.5)wy 至少包含一個標(biāo)記字符(8.6)wxy 包含不超過 n 個標(biāo)記字符(8.7)x 至少包含一個標(biāo)記字符(8.8)vw mxy mz L(G), m>=0(8.9)證明：類似泵引理的證明，設(shè)接受L- 的 CNF 形式的 CFG 有 p 個非終結(jié)符，令 n=2p+1 ，設(shè) u L, |u|>=n ，且 u 上 n 個字符作了標(biāo)記，在泵引理的證明中，我們選擇最

19、長的路徑，它自動滿足條件 (8.5)和 (8.9)，為了滿足 (8.6)-(8.8) ，我們需要更仔細地選擇路徑。從根節(jié)點出發(fā)，每次我們選擇子樹的葉節(jié)點標(biāo)記多的子節(jié)點，擴充進路徑。如果內(nèi)部節(jié)點的兩個子節(jié)點對應(yīng)的子樹都帶有標(biāo)記的葉節(jié)點，則稱為branch point 。按照我們的選法，每個新加入路徑的節(jié)點含有的標(biāo)記葉節(jié)點至少是它的父節(jié)點含有的數(shù)目的一半。在這種情況下，可以應(yīng)用下面的引理來完成證明（類似定理8.1 的證明用到了引理 8.1）。引理 8.2 d 是二叉樹上的一個路徑，r 是 d 上的一個接點，如果r 的后代包含 <=h 個 branchpoint ，則 r 為根的樹包含 <

20、;=2 h 個標(biāo)記葉節(jié)點。證明：整個證明很類似引理8.1，對 branch point 的個數(shù)使用數(shù)學(xué)歸納法，且把葉節(jié)點的數(shù)目改成標(biāo)記葉節(jié)點。 此處是 2h 而不是 2h-1 的原因是我們把葉節(jié)點排除在branch point 之外。如果帶標(biāo)記的葉節(jié)點也稱為branch point ，那么本命題中的branch point 實際上是 h+1 個。繼續(xù)定理 8.2 的證明，引理8.2 說明在我們選擇的路徑上至少有p+1 個 branch point，由于只有 p 個不同的非終結(jié)符， 因此至少有兩個 branch point 是相同的非終結(jié)符， 則我們類似定理證明中 v, w, x, y, z 的

21、選取，根據(jù) branch point 的定義，上面的 (8.6)-(8.8) 式顯然成立。值得注意的是，普通的泵引理可以看成Ogden 定理的特殊情況，即如果字符串上所有的字符都作標(biāo)記，就自然得到了泵引理。例子 8.5 語言 L=a ibicj | i,j>=0 and ji 不是 CFL 。分析：反證法。假設(shè)L 是 CFL ，根據(jù)定理8.2，存在 n，選擇 u=anbncn+n! ，我們將前面的n個 a 作標(biāo)記，根據(jù)定理 8.2，存在 5 個字符串 v, w, x, y, z 。滿足 (8.5)-(8.9) 式。分情況討論：1. w 或 y 包含不同的字母，則 vw 2xy 2z L

22、（不再是 a*b*c* 的形式）。2. 由于 wy 至少含有一個標(biāo)記字符 a，則只可能 w=aj, y=b j，當(dāng) m 足夠大時，如 m=n!/j+1 ， vw mxy mz L。問題：例子8.5 可以用普通的泵引理來說明嗎？例子 8.6 語言 L=a pbqcrds | p=0 or q=r=s 不是 CFL 。分析： 例子 8.1 說明了 b qcqdq 不是 CFL ，似乎預(yù)示了L 也不是 CFL 。本例先說明L 滿足普通泵引理，因此不能用普通泵引理說明L 不是 CFL。設(shè) n 是任意的正整數(shù)， 任給 uL, |u|>=n ，設(shè) u= apbqcrds，則我們都能找到5 個字符串

23、v, w, x,y, z 滿足式子 (8.1)-(8.4) 。如果 p=0，則令 w=b, v=x=y=, z=bq-1crds, vw mxy mz=bm+q-1 cr ds L ；如果陶曉鵬Copyright 20034語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言p>0，則令 w=a, v=x=y=, z=ap-1bqcrds, vw mxy mz=am+p-1 brcrds L ?，F(xiàn)在我們使用定理8.2，設(shè) L 是 CFL ，根據(jù)定理 8.2 存在 n，令 u=abncndn，除了第一個字符a，其他字符都作標(biāo)記。設(shè)存在v, w, x, y, z 滿足 (8.5)-(8.9)

24、式，則 wy 至少包含 b, c, d 中的一個，但不能三個都包含，則vw 2 xy2z 包含一個 a，但 b, c, d 的數(shù)目不相等，不屬于 L 。8.2上下文無關(guān)語言的交集和補集根據(jù)定理6.1， CFL 在合并、連接和Kleene* 運算下保持封閉性。對于正則語言，保持封閉性的運算還可以增加兩個：交集和補集。 CFL 是更復(fù)雜的語言，它在交集和補集運算下不一定保持封閉性。定理 8.3 存在兩個 CFL L1 和 L2 ，它們的交集 L1 L2 不是 CFL 。存在 CFL L ，它的補集 L 不是 CFL 。證明：我們利用例子 8.3構(gòu)造 CFL 如下，L 1=a ibjck| i<

25、;jL 2=a ibjck| i<k則 L 1L2i j k=a b c | i<j and i<k例子 8.3的方法可以證明L1 L2 不是 CFL。L1 和 L2 是 CFL ，它們分別可由下面的兩個CFG 生成。CFG G1: S ABCA aAb |B bB | bC cC |CFG G2: SACAaAc | BBbB |CcC | c此處省略 CFG G1 和 G2 分別生成語言L1 和 L2 的證明?，F(xiàn)在證明第二個命題， 用反正法， 由于 L 1 L 2=(L 1 L2 ，)假設(shè) CFL L 的補集仍然是CFL ，那么 L 1和 L 2也是 CFL ，根據(jù)合并運

26、算保持CFL 的封閉性， (L 1 L2 也)是 CFL ，即 L 1L 2 是CFL ，這與前面證明的結(jié)論矛盾，因此假設(shè)不成立。例子 8.7 定理 8.3 證明第二個命題用的是反證法，而不是構(gòu)造性證明，它能夠證明結(jié)論，但不能揭示問題出在什么地方。分析：令 R=a*b*c* ，則 L 1 =Ra ibjck| i>=j ，由于 R 是正則語言，因此R也是正則語言，同時也是 CFL 。另外， a ibjck | i>=j=a m| m>=0a jbj | j>=0ck | k>=0，根據(jù) CFL 在連接運算下的封閉性， ai j k 也是 CFL 。類似的方法能夠說

27、明2也是 CFL ，因此12i j kb cLL L =Ra b c| i>=j or i>=k 也是 CFL 。而 (L 1 L 2 不)是 CFL ?？梢娗懊鎯纱蔚难a集保持了CFL 的性質(zhì)，最后一個補集失去了 CFL 的性質(zhì)?；叵攵ɡ?3.4，兩個正則語言的交集仍然是正則語言，我們在已有的兩個FA 上構(gòu)造了接受交集語言的 FA ，那么為什么 PDA 無法完成類似的構(gòu)造呢？在構(gòu)造FA 時，我們定義了新的狀態(tài)(p, q)，用這個 2 元組同時跟蹤原來FA 的狀態(tài)變化，當(dāng)p 和 q 都處于接受狀態(tài)時，新FA 就到達了接受狀態(tài)。類似地，設(shè)接受 CFL L1 和 CFL L2的 PDA

28、分別是 M1=(Q1, , q1, Z1, A1,1)和 M2=( Q2, , q2, Z2, A2, 2)，新的 PDA 的狀態(tài)集 Q=Q1 Q2，我們還需要跟蹤棧的變化情況。根據(jù)7.1節(jié)的討論， 我們可以嚴(yán)格地限制棧頂處理的規(guī)則，比如只允許壓入或彈出操作，而不會影響 PDA陶曉鵬Copyright 20035語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言識別語言的能力，因此M1 和 M2 輸入同一個字符a 時都只有兩種移動，而轉(zhuǎn)移函數(shù)則分別有四種可能，1(p, a, X)=| (p , X | X)(p ,) | (p , X X), (p) ,2(q, a, Y)=| (q Y, Y

29、) | (q , ) | (q , Y Y), (q) ,那么如何求(p,q), a, (X,Y) ？ 1和 2 的組合有16 種情況，我們用下面的表討論的計算。1 (p , X X) (p ,)(p ,X X),2(p , ) (q Y, Y)( (p , q),(X ,Y) )(X,Y), ),Y ( )(X, Y)?( (p , q?(q , )( (p , q ), )(X, Y)?,(p , q ),(q , Y Y), (q) ,?另一種計算方式是，1 (p , X X) (p ,)(p ,X X),2(p , ) (q Y, Y)( (p , q ), (X )X, Y Y),

30、),Y ( )?Y)?( (p , q?(q , )( (p , q ), (X )? X,(p , q ),(q , Y Y), (q) ,?可見我們無法用一個棧模擬兩個棧的變化，比如一個棧要壓入，另一個棧要彈出，那么用于模擬的棧應(yīng)該壓入還是彈出？顯然， 兩個 PDA 中，其中一個沒有?；驐?nèi)容沒有變化， 則能夠構(gòu)造同時跟蹤它們的 PDA ，因此有下面的定理。定理 8.4 L1 是 CFL ， L2 是正則語言，則L1 L2 是 CFL。證明：用構(gòu)造法證明。設(shè)接受L1 的 PDA M1=(Q1, , q1, Z0,A1, 1)，接受 F2 的 FAM2=(Q2, q2, A2,2) （注意，

31、此處的FA 是沒有空轉(zhuǎn)移的確定型FA ）。構(gòu)造接受L1 L2的PDA M=(Q, , q0, Z0, A,)如下，Q=Q1 Q2q0=(q1, q2)A=A1 A2(p, q), a, Z)=(p)| (p,q),1(p, a, Z) and 2(q, a)=q (1)(p, q), Z)=(p , q),| (p) , 1(p, , Z)(2)其中， pQ1, qQ2, Z, a。我們看到 M 的狀態(tài)跟蹤了 M1和 M2 的狀態(tài)的變化， M 的棧跟蹤了M1 的棧的變化。為了證明 M 接受 L1 L2，我們證明一個更普遍的結(jié)論：字符串y 使得 M1到達狀態(tài) p，且棧內(nèi)容為，使得M2 到達狀態(tài)

32、q，當(dāng)且僅當(dāng) y 使得 M 到達狀態(tài) (p, q) ，且棧內(nèi)容為。用數(shù)學(xué)語言描述如下，任給 n>=0, p Q1, qQ2, y,z*,* ，那么， (q1, yz, Z 1)nM1 (p, z,)且 2*(q 2, y)=q ，當(dāng)且僅當(dāng)， (q1 21nM(p,q), z,)。,q), yz, Z )這里 n 表示移動的步數(shù)，對 n 使用數(shù)學(xué)歸納法，我們證明必要性。=Z1, q=q2 ，則得到，1.n=0， (q , yz, Z )0M1(p, z,)且*(q2, y)=q ，顯然 y= , p=q1,112(q1, q2), yz, Z1)0M (q1, q2), z,)=(q1,

33、q2), yz, Z1) ，得證。k+1M12.設(shè) k>=0, n=k時命題成立，要證明 n=k+1 時也成立。設(shè) (q1, yz, Z1)(p, z,2)且 *(q2,y)=q ，考慮 M 1 在 k+1 步移動中的最后一步，如果是空移動，則(q1, yz, Z1)kM1(p , z,)M1 (p, z, )陶曉鵬Copyright 20036語言與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言根據(jù)歸納假設(shè)有， (q1, q2), yz, Z1)kM (p , q), z,) ，根據(jù)轉(zhuǎn)移函數(shù)(2)有，(p , q), z,)M (p, q), z,)，得證。如果最后一步不是空轉(zhuǎn)移，令y=

34、ya, a ，有(q1, yz, Z1)kM1 (p az, )M1 (p, z,)設(shè) q=(q1, q2), yz, Z1)k2*(q 2, y )，根據(jù)歸納假設(shè)有，M (p , q ),，az,再根據(jù)轉(zhuǎn)移函數(shù) (1) 有，(p , q ), az,M (p, q), z,)，得證。充分性證明省略。受到定理8.4 證明的啟發(fā)，我們再考慮一下是什么原因?qū)е翪FL 的補集不一定是CFL 。對于 FA M=(Q, q0, A,)，我們只要略作修改M=( Q, q0, Q-A,)，則 M接受的語言就是L(M)的補集。那么類似地， 對于 PDA M=(Q, q0, Z0, A,)，同樣的修改得到M=(

35、 Q, q0, Z0,Q-A, )， M接受的語言是否是 L(M) 的補集呢？定理 8.3 證明了不一定，原因在于 PDA 的不確定性，比如存在(q0, x, Z0)*M (p,)，也存在(q0, x, Z0)*M (q,)，pA 且 qA ，此時 xL(M) ，而按照上面的構(gòu)造方法，也有xL(M)。而 FA 盡管也有非確定型FA ，但都能發(fā)現(xiàn)等價的確定型FA ，因此能夠避免這種現(xiàn)象。那么是不是確定型PDA（DPDA ） M 接受的語言L 的補集，可以通過上面方法構(gòu)造的PDAM來接受呢？答案仍然是否定的，這是因為一個不被M 接受的字符串x 可能導(dǎo)致M 出現(xiàn)無限移動， 那么 x 同樣導(dǎo)致M出現(xiàn)無

36、限移動，因此也不能被M接受（ FA 上不可能出現(xiàn)無限轉(zhuǎn)移的情況）。利用練習(xí) 7.27 的結(jié)論可以解決DPDA 無限移動的問題， 因此可以構(gòu)造接受補集的DPDA 。這說明了確定型上下文無關(guān)語言（DCFL ）的補集也是DCFL ，特別地，如果一個CFL 的補集不是 CFL ，則該 CFL 不是 DCFL （定理 8.3 和例子 8.7）。8.3與上下文無關(guān)語言相關(guān)的判定問題在第 5 章最后部分，我們考察了許多涉及正則語言的判定問題，其中第一個問題就是成元資格問題，這些問題可以類似地放到 CFL 上。我們將發(fā)現(xiàn)，有些問題可以用相似的方法解決，有些問題涉及到 CFL 內(nèi)在不確定性帶來的差異，需要尋找新

37、方法，還有些問題，可能沒有辦法解決，這需要用到更復(fù)雜的計算模型來證明。對于 CFL 基本的乘員資格問題，即任給一個PDA M 和字符串x，M 是否接受 x，原來得簡單的方法： 將 x 放入 M 運行，不再是可行的辦法。8.2 節(jié)我們已經(jīng)提到，由于 PDA 的非確定性，一個不被接受的字符串可能導(dǎo)致M 無限移動， 盡管可能存在某個移動到達拒絕狀態(tài)，但仍然要等待其他移動結(jié)束后，才能判斷 x 是否屬于L(M) 。我們可以在DPDA 上解決這個問題，另外我們從 CFG 的角度討論，借助第6 章的結(jié)論，如果一個CFG 沒有空產(chǎn)生式和單一產(chǎn)生式，則生成長度為 n 的字符串的推導(dǎo)步驟至多2n-1 步。而對每個

38、PDA 都能構(gòu)造出對應(yīng)的CFG，因此可以通過 CFG 來解決這個問題。成員資格問題的判定算法（給定一個PDA M 和字符串 x， M 是否接受 x？）定理 7.4 給出了從 PDA M 構(gòu)造 CFG G 的算法，且 L(G)=L(M) 。如果待判定的字符串x= ，則用 FindNull 算法（見 6.6 節(jié)）確定 G 的起始非終結(jié)符是否是可空非終結(jié)符；否則利用算法 6.1和算法 6.2 去掉G 中的空產(chǎn)生式和單一產(chǎn)生式，得到新文法G，然后用 G完成從 1 步到 2|x|-1步的所有推導(dǎo)，如果發(fā)現(xiàn)其中一個推導(dǎo)生成了x，則 xL(M) ，否則 xL(M) 。陶曉鵬Copyright 20037語言

39、與計算理論導(dǎo)引上下文無關(guān)語言與非上下文無關(guān)語言我們考察對應(yīng)第5 章問題 1 和問題 2 的兩個與CFL 相關(guān)的問題：1. 給定一個 CFG G ， L(G)= ?2. 給定一個 CFG G ， L(G) 是否是有限集？定理 8.1 提供了回答這兩個問題的方法。首先將G 轉(zhuǎn)換成 CNF 形式的 CFG G，設(shè) p 是 G的非終結(jié)符的個數(shù)，令n=2 p+1。如果G能夠生成某個字符串，則它一定能夠生成某個長度<=n的字符串，否則應(yīng)用泵引理能夠不斷找到更短的屬于L(G)的字符串；類似地，如果G能夠生成無限多的字符串， 那么一定能夠生成一個長度在 n 和 2n 之間的字符串， 證明基本完全像同于第

40、 5 章的證明。因此我們得到下面的兩個判定算法。問題 1 和問題 2 的判定算法（ L(G)=?L(G) 是否有限 ?）算法梗概：首先檢測是否屬于L(G) ，如果是，則L(G)。然后構(gòu)造G 的 CNF G， 設(shè) p是 G的非終結(jié)符的個數(shù)，令 n=2 p+1，檢測是否有長度為1 到 n 的字符串是否屬于G，如果沒有，且L(G)，則 L(G)=，如果有，則繼續(xù)檢測是否有長度為n 到 2n 的字符串屬于G，如果沒有，則 L(G)是有限集，否則是無限集。問題：寫出上面的算法，分析算法的時間復(fù)雜性。上面的算法思路簡單，但執(zhí)行效率很低，所幸的是，目前已經(jīng)提出了不少高效算法，特別是針對成員資格問題（參見Earley 論文， Communication of the ACM 13(2): 94-102, 1970）。如果我們繼續(xù)第5 章列出的單子，解決它們對應(yīng)于CFL 的問題，我們會發(fā)現(xiàn)有些問題沒有解決的方法，哪怕是很低效的方法。比如，給定兩個CFG，它們生成的語言的交集是否為空？第5 章的算法基礎(chǔ)是正