1、.第三章 上下文無關語言3.1略。3.2a. 利用語言 A=a mbncn | m,n 0 和 A=a nbncm | m,n 0 以及例 3.20，證明上下文無關語言在交的運算下不封閉。b. 利用 (a)和 DeMorgan 律 (定理 1.10)，證明上下文無關語言在補運算下不封閉。證明： a.先說明 A,B 均為上下文無關文法，對A 構造 CFG C1SaS|T|TbTc|對 B,構造 CFG C2SSc|R|R aRb由此知 A,B 均為上下文無關語言。但是由例 3.20, A B=a nbn cn |n 0 不是上下文無關語言，所以上下文無關語言在交的運算下不封閉。b.用反證法。假設

2、 CFL 在補運算下封閉， 則對于 (a)中上下文無關語言A,B ，A , B也為 CFL ，且 CFL 對并運算封閉，所以 AB 也為 CFL，進而知道 AB 為 CFL，由 DeMorgan 定律 A B A B，由此 A B 是 CFL,這與 (a)的結論矛盾，所以CFL 對補運算不封閉。3.3 略。3.4 和 3.5 給出產生下述語言的上下文無關文法和PDA，其中字母表=0,1 。a.w | w 至少含有 3 個 10,1SA1A1A1A1,A0A|1A|,1,1,1b.w | w 以相同的符號開始和結束 S0A0|1A10,A0A|1A|0,1,0,001,11,1c.w | w 的

3、長度為奇數 0,S0A|1A1,A0B|1B|B0A|1A0,1,1 / 9.d.w | w 的長度為奇數且正中間的符號為0S0S0|1S1|0S1|1S0|00,00,01,01,0, $0,$e.w | w 中 1 比 0 多SA1A1,0A0A1|1A0|1A|AA|0,100,11,1,$,1,$f. w | w=w RS0S0|1S1|1|00,00,01,11,1, $1,$0,g. 空集SS3.6 給出產生下述語言的上下文無關文法：a 字母表 a,b 上 a 的個數是 b 的個數的兩倍的所有字符串組成的集合。S bSaSaS|aSbSaS|aSaSbS|nnb語言 a b |n

4、0 的補集。見問題3.25 中的 CFG:T aT|bT|cw#x | w, x0,1 * 且 wR 是 x 的子串 。S UVU 0U0|1U1|WW W1|W0|#V 0V|1V|dx 1#x2#xk|k 1, 每一個 xia,b * , 且存在 i 和 j 使得 xi xjR 。UA|A aA|bA|#A|# V aVa|bVb|#B|# BaB|bB|#B|# WB|3.7 略。2 / 9.3.8 證明在 3.1 節開始部分給出的文法G2 中，字符串 the girl touches the boy withthe flower 有兩個不同的最左派生，敘述這句話的兩個不同意思。<

5、句子 ><名詞短語 ><動詞短語 ><復合名詞 ><動詞短語 ><冠詞 ><名詞 ><動詞短語 >a_<名詞 >< 動詞短語 >a_girl_<動詞短語 >a_girl_<復合名詞 >a_girl_<動詞 >< 名詞短語 >a_girl_touches_< 名詞短語 >a_girl_touches_<復合名詞 ><介詞短語 >a_girl_touches_<冠詞 >< 名詞 >

6、;<介詞短語 >a_girl_touches_the_<介詞 ><復合名詞 >a_girl_touches_the_boy_<介詞短語 >a_girl_touches_the_boy_<介詞 >< 復合名詞 >a_girl_touches_the_boy_with_<復合名詞 >a_girl_touches_the_boy_with_<冠詞 >< 名詞 >a_girl_touches_the_boy_with_the_<名詞 >a_girl_touches_the_boy_w

7、ith_the_flower含義是：女孩碰這個帶著花的男孩<句子 ><名詞短語 ><動詞短語 ><復合名詞 ><動詞短語 ><冠詞 ><名詞 ><動詞短語 >a_<名詞 >< 動詞短語 >a_girl_<動詞短語 >a_girl_<復合動詞 >< 介詞短語 >a_girl_<動詞 >< 名詞短語 ><介詞短語 >a_girl_touches_< 名詞短語 ><介詞短語 >a_gir

8、l_touches_<冠詞 >< 名詞 ><介詞短語 >a_girl_touches_the_<名詞 ><介詞短語 >a_girl_touches_the_boy_<介詞短語 >a_girl_touches_the_boy_<介詞 >< 復合名詞 >a_girl_touches_the_boy_with_<復合名詞 >a_girl_touches_the_boy_with_<冠詞 >< 名詞 >a_girl_touches_the_boy_with_the_<

9、;名詞 >a_girl_touches_the_boy_with_the_flower含義是：女孩用花碰這個男孩3.9 給出產生語言 A=a i bjck| i,j,k 0 且或者 i=j 或者 j=k 的上下文無關文法。 你給出的文法是歧義的嗎？為什么？解：下面是產生A 的一個 CFG:3 / 9.S UV|ABU aUb| V cV| A aA|BbUc|這個 CFG 是歧義的，因為字符串abc 有如下兩種不同的最左派生：SUVaUbVabVabcVabcSABaAVaVabVcabc3.10給出識別 3.9 中語言 A 的下推自動機的非形式描述。解：其非形式描述為：此 PDA 有兩

10、個非確定性的分支： 一個分支先讀 a，并且每讀一個 a 將一個 a 推入棧中，當碰到 b 時，每讀一個 b 從棧中彈出一個 a，若沒有 a 可彈出則拒絕，最后讀 c 且不改變棧中的內容，若此時棧為空則接受。另一個分支也是先讀 a，但不改變棧中內容，當碰到 b 時，每讀一個 b 將一個 b 推入棧中，再讀 c, 每讀一個 c 從棧中彈出一個 b，若沒有 a 可彈出則拒絕，若 c 讀完后棧為空則接受。開始時，讀輸入串的字符， 非確定性的選擇一個分支運行， 若有一個分支接受則接受，否則拒絕。3.13 設有上下文無關文法G:STT|UU0U00|#T0T|T0|#a.用普通的語言描述L(G) 。b.證

11、明 L(G) 不是正則的。解：a. A=0 i #0j #0k | i, j, k 00 i #02i | i 0 。p2pnp+i2pb. 取 s=0 #0 , 則對于任意劃分 s=xyz(|xy| p, |y|>0), xy z=0#0A,所以不是正則的。3.14 用定理 3.6 中給出的過程，把下述CFG 轉換成等價的喬姆斯基范式文法。ABAB|B|B00|解：添加新起始變元S0,去掉 BSASA00ABAB|B|ABAB|AB|BA|B|B00|B00去掉A ,去掉A BS0AS0AABAB|AB|BA|B|BBABAB|AB|BA|00|BBB00B004 / 9,.去掉 S0

12、 A,添加新變元S0BAB|AB|BA|00|BBS0VB|AB|BA|UU|BBABAB|AB|BA|00|BBAVB|AB|BA|UU|BBB00BUUVBAU0問題3.15 證明上下文無關語言類在并,連接和星號三種正則運算下封閉。a.AB方法一： CFG。設有 CFG G1 (Q1, ,R1,S1) 和 G2=(Q2, ,R2,S2)且 L(G 1)=A, L(G 2)=B。構造 CFG G=(Q, ,R,S0)，其中Q= Q1Q2S ,S是起始變元， R= R R2S0S|S.00112方法二： PDA。設 P1=(Q1, , 1, 1,q1,F1)識別 A ， P2=(Q1, , 2

13、, 2,q2,F2)是識別 B。則如下構造的 P=(Q, , , ,q0,F)識別 A B，其中1) Q=Q1 Q2 q 0 是狀態集，2) 12，是棧字母表，3) q0 是起始狀態，4) F F1 F2 是接受狀態集，5) 是轉移函數，滿足對任意 q Q, a,b( q1, ), ( q2 ,), 若 qq0 , ab,(q,a,b)=1 (q, a, b),若 qQ1 , b(1 ),2 ( q, a, b),若 qQ2 , b(2 ),else.b. 連接 AB方法一： CFG。設有 CFG G1 (Q1, ,R1,S1) 和 G2=(Q2, ,R2,S2)且 L(G 1)=A, L(G

14、 2)=B。構造 CFG G=(Q, ,R,S0)，其中Q= Q1Q2S ,S是起始變元， R= R R2S0SS.00112方法二： PDA。設 P1 =(Q1, , 1, 1,q1,F1)識別 A ，P2=(Q1, , 2, 2,q2,F2)是識別 B，而且 P1 滿足在接受之前排空棧 (即若進入接受狀態，則棧中為空 )這個要求。則如下構造的 P=(Q, , , ,q1,F)識別 A B，其中1) Q=Q1 Q2 是狀態集，2) 12，是棧字母表，3) q1 是起始狀態，4) F F1 F2 是接受狀態集，5)是轉移函數，滿足對任意qQ, a,b5 / 9.1 (q, a, b),若q Q

15、1F1 , b(1),1( q, a,b)( q2 ,),若q F1, ab,(q,a,b)=1 (q, a, b),若q F1, (a, b)(,),2 ( q, a,b),若q Q2 , b( 2 ),else.c. A*111，1。構造0，方法一：CFG。設有 CFG G1其中 Q=QS ,S(Q, ,R ,S)L(G )=ACFG G=(Q, ,R,S )是起始變元， R= RS0SS|S| .1001001方法二： PDA。設 P1=(Q1, , 1, 1,q1,F1)識別 A ，而且 P1 滿足在接受之前排空棧 (即若進入接受狀態，則棧中為空 )這個要求。則如下構造的 P=(Q,

16、, , ,q1,F)識別 A * ，其中1) Q=Q1 q 0 是狀態集，2) 1，是棧字母表，3) q0 是起始狀態，4) F F1 q 0 是接受狀態集，5)是轉移函數，滿足對任意qQ, a,b1 ( q, a, b),若qQ1F1,1 ( q, a, b)( q1 , ),若qF1, ab,(q,a,b)=1 ( q, a, b),若qF1 , (a, b)( , ),( q1 , )若qq0 , ab,else.3.16先說明如何把正則表達式直接轉換成等價得上下文無關文法，然后利用問題 3.15 的結果，給出每一個正則語言都是上下文無關文法的一個證明。解：設有正則表達式 T，將其轉化為

17、上下文無關文法。1) 首先添加 S T，且令 S 為起始變元。2) 根據 T 的不同形式，按如下方式添加規則 若 Ta ， 則在規則集中添加 T a,若T，則在規則集中添加 T,若T，則在規則集中添加 TT， 若 TA B，則在規則集中添加 TA|B ， 若 TA·B,則在規則集中添加 TAB ， 若 TA*,則在規則集中添加 TA,和 A AA|3) 若有新添加的變元，則根據其所對應的表達式轉第2 步，直到沒有新的變元出現。下面來證明每一個正則語言都是上下文無關的由正則語言與正則表達式的等價性可知： 對于一個正則語言都存在一個描述他的正則表達式， 由前述討論可知， 這個正則表達式可

18、轉換為一個與之等價的上下文無關的文法。 因此，此正則語言能由這個上下文無關文法產生。 所以正則語6 / 9.言是上下文無關的。3.17 a. 設 C 是上下文無關語言， R 是正則語言。證明語言 C R 是上下文無關的。b 利用 a 證明語言A=w | wa,b,c * , 且含有數目相同的 a,b,c2 2 2是識別證明： a. 設 P=(Q1, , ,1 11是一個識別C的，2, ,R,q ,F )PDA N=(Q,q ,F )的一臺 NFA。下面構造識別 CR 的 PDA 如下 S=(Q, , ,q0,F):1) Q=Q1×Q2, 是狀態集，2) q0=(q1,q2)是起始狀態

19、，3) F= F1×F2, 是接受狀態集，4) 是轉移函數，滿足對任意 q Q1,r Q2,a ,b ,(q,r),a,b)=(q ,r),c) | q 1(q,a), (r,c)2(r,a,b).b. Aa* b* c* =a nbncn|n 0,若 A是 上下文無關的， 則由a 中命題知anbncn|n 0 也是上下文無關的，矛盾。3.18 用泵引理證明下述語言不是上下文無關的：a. 0 n1n0n1n | n 0假設語言上下文無關，設 p 為泵長度，取 S=0p1p 0p1p . 由泵引理知， S 可以劃分為 uvxyz 且滿足泵引理條件。考察子串 vxy, 首先，它一定橫跨

20、S 的中點，否則，若 vxy 位于 S 的前半段，由于 |vxy| p, 則 uv2xy 2z 中 1 將是后半段字符串的第一個字符，即不可能是 0n1n0n1n 的形式。同理， vxy 也不可能位于 S 后半段的位置上。但是 , 若 vxy 跨越 S 的中點時，將 S 抽取成 uxz，它形如 0p 1i 0j 1p,i ，j 不可能都為 p，即 uxz 不可能是 0n1n0n1n 的形式。綜上，可知 S 不能被抽取，因此，該語言不是上下文無關的。b. 0 n#02n#03n | n 0假設語言上下文無關，設p 為泵長度，取 S=0p#02p#03p,由泵引理知， S 可以劃分為 uvxyz

21、且滿足泵引理條件。考察子串 vxy 。首先， v,y 中不能有 #，否則 S 抽取成 uxz 后，其中 #個數 1。由條件 3， vxy 或者位于第 2 個#之前，或者位于第 1 個 #之后。下面討論這兩種情況： 此時， uv2 xy2z 中第 3 部分 0 的個數保持不變，而前面部分的0的個數至少有一個增加，因此， uv2xy 2z 不在該語言中。 此時， uv2xy2z 中第 1 部分 0 的個數保持不變，而第2，3 部分0 的個數至少有一個增加，也有 uv2 xy2z 不在該語言中。因此，該語言不是上下文無關的。c. w#x | w,xa,b *, w 是 x 的子串 假設該語言上下文無

22、關，設 p 為泵長度，取 S=0p1p#0p1p , 由泵引理知， S 可以劃分為 uvxyz 且滿足泵引理條件。顯然， v,y 中不包含 #，不然抽取后的 S=uxz 中將不含 #從而不在該語言中。子串 vxy 不能落在 #的左側，否則 uv2xy 2z 中#左側的字符串長度將大于右邊。子串 vxy 不能落在 #的右側，否則 uxz 中#左側的字符串長度也會大于右邊。現在假設 # x，則必存在不全為 0 的 i,j ，使得 vy=1i0j ，下面分兩種情況考慮： j 0, 則 uxz=0p1p-i#0p-j1p 不在該語言中 j=0, 則 uv2xy2z 中 #左側的字符串長度大于右邊，不在

23、該語言中。7 / 9.因此，該語言不是上下文無關的。12k| k 2, 每一個 xia,b*ixjd. x#x #x, 且存在 x假設該語言上下文無關，設p 為泵長度，取 S=apbp#apbp ,由泵引理知， S 可以劃分為 uvxyz 且滿足泵引理條件。顯然， v,y中不包含 #，不然抽取后的 S=uxz 中將不含 #從而不在該語言中。22子串 vxy 不能落在 #的左側，否則 uv xy z 中#左側的字符串長度將大于右邊。于是 vxy 跨越 #兩側 . 此時，S 經抽取成 uxz 后，具有 apbi #aj bp 的形式，其中， i,j 不全為 p。因此， uxz 不在該語言中。綜上該

24、語言不是上下文無關的。3.19證明：設 G 是一個 Chomsky 范式 CFG，則對任一長度2 的字符串 wL(G),w 的任何派生恰好有2n1 步。證明： (用數學歸納法 )當 n=2 時，對于 Chomsky 范式 CFG ，長度為 2 的字符串必由 3 步派生，此時命題為真。k+1，假設當 2n k 時命題為真。 當 n=k+1 時，對于長度為 k+1 的字符串 s=s1 2存在 S的一個直接派生S AB ，使得 A 產生子串 s ssss ， B 產生子串001 2psp+1sp+2sk+1，其中 1 p k+1。由歸納假設， A 產生子串 s1s2sp 需要 2p-1 步派生，而

25、B 產生子串 sp+1 p+2k+1需要2(k+1-p)-1步派生。因此，0 產生字符串s 共需ssS2(k+1)-1 步派生。即當 n=k+1 時命題亦真。因此，由 G 產生長度為 n 2 的字符串需要2n-1 派生。3.20 設 G 是一個含有 b 個變元的喬姆斯基范式CFG。證明：如果 G 產生某個字符串使用了至少2b 步的派生，則 L(G) 是無窮的。T證明：設 G 產生字符串 S 需要至少 2b 步。由于一個分支點 (變元 )對應一次派生，所以 S 的語法樹至少有 2b 個分支點。又由于在喬姆斯基范式下，一R個分支點至多有兩個子分支點 (這意味著層數n 的結點個數 2b1)，從而的由

26、分支點組成的子樹的高度R大于等于 b+1。有一條路徑上分支點(變元 )個數b+1。由鴿巢原理：必有某個變元 R 在該路徑上出現至少兩次。不妨假設 R 出現在路徑上最下面的b+1 個u v xy z變元中。按上圖所示，將S 劃分為 uvxyz，在每一個 R 的下面有一棵子樹，它產生S 的一部分。上面的 R 有一棵較大的子樹， 產生 vxy ，下面的 R 有一棵較大的子樹，產生 x，由于這兩棵子樹由同一個變元產生，因而可以相互替換。這里采用如下操作：反復用較大子樹去替換較小子樹， 則我們得到對于任意 n>1, uv nxy nz L(G) 。所以若我們能證明 v,y 不全為，則 L(G) 是無窮的。事實上，由喬姆斯基范式的特點，上面一個R 的派生選擇的必為RAB 形式的規則，而且不可能有A和 B，所以 v,y 不全為 。從而命題得證。3.22 考慮語言 B=L(G), 其中 G 是練習 3.13 中給出的文法。定理 3.19 關于上下文無關語的泵引理稱存在關于 B 的泵長度 p。p 的最小值等于多少？要求給出證8 / 9.明。證明：p 的最小值為 4。令 D=0 i #0j #0k | i, j, k 0, E=0 i #02i | i 0, 則 L(G)=DE。L(G)中長度為 1 的字符串僅有 #,不