计算理论课后题及答案.docx

1、计算理论课后题及答案第三章 上下文无关语言3.1 略。3.2 a. 利用语言A=ambncn | m,n 0和A=anbncm | m,n 0以及例3.20，证明上下文无关语言在交的运算下不封闭。b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1S aS|T| T bTc| 对B,构造CFG C2S Sc|R| R aRb由此知 A,B均为上下文无关语言。但是由例3.20, AB=anbncn|n 0不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封

2、闭，则对于(a)中上下文无关语言A,B，,也为CFL，且CFL对并运算封闭，所以也为CFL，进而知道为CFL，由DeMorgan定律AB，由此AB是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。3.3 略。3.4和3.5 给出产生下述语言的上下文无关文法和PDA，其中字母表 =0,1。a.w | w至少含有3个1SA1A1A1AA0A|1A| b.w | w以相同的符号开始和结束S0A0|1A1A0A|1A| c.w | w的长度为奇数S0A|1AA0B|1B| B0A|1Ad.w | w的长度为奇数且正中间的符号为0S0S0|1S1|0S1|1S0|0e.w | w中1比0多SA1

3、AA0A1|1A0|1A|AA| f.w | w=wRS0S0|1S1|1|0g.空集SS3.6 给出产生下述语言的上下文无关文法：a字母表a,b上a的个数是b的个数的两倍的所有字符串组成的集合。 SbSaSaS|aSbSaS|aSaSbS| b语言anbn|n 0的补集。见问题3.25中的CFG:SaSb|bY|TaTaT|bT| cw#x | w, x 0,1*且wR是x的子串。SUVU0U0|1U1|WWW1|W0|#V0V|1V| dx1#x2# #xk|k 1, 每一个xi a,b* , 且存在i和j使得xixjR。SUVWUA| AaA|bA|#A|#VaVa|bVb|#B|#Ba

4、B|bB|#B|#WB| 3.7 略。3.8 证明在3.1节开始部分给出的文法G2中，字符串the girl touches the boy with the flower有两个不同的最左派生，叙述这句话的两个不同意思。 a_ a_girl_ a_girl_ a_girl_ a_girl_touches_ a_girl_touches_ a_girl_touches_ a_girl_touches_the_ a_girl_touches_the_boy_ a_girl_touches_the_boy_ a_girl_touches_the_boy_with_ a_girl_touches_th

5、e_boy_with_ a_girl_touches_the_boy_with_the_ a_girl_touches_the_boy_with_the_flower含义是 ：女孩碰这个带着花的男孩 a_ a_girl_ a_girl_ a_girl_ a_girl_touches_ a_girl_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_

6、the_boy_with_the_ a_girl_touches_the_boy_with_the_flower含义是： 女孩用花碰这个男孩3.9 给出产生语言A=aibjck| i,j,k 0且或者i=j或者j=k的上下文无关文法。你给出的文法是歧义的吗？为什么？解：下面是产生A的一个CFG:S UV|ABU aUb| V cV| A aA| B bUc| 这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生：S UV aUbV abV abcV abcS AB aAV aV abVc abc3.10 给出识别3.9中语言A的下推自动机的非形式描述。解：其非形式描述为：此PDA有两个

7、非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c, 每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。3.13 设有上下文无关文法G:S TT|UU 0U00|#T 0T|T0|#a.用普通的语言描述L(G)。b.证明L(G)不是正则的。解： a. A=0i#0j#0k | i

8、, j, k 0 0i#02i | i 0。 b. 取s=0p#02p, 则对于任意划分s=xyz(|xy| p, |y|0), xynz=0p+i#02p A, 所以不是正则的。3.14 用定理3.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。A BAB|B| B 00| 解：添加新起始变元S0, 去掉B S0 A S0 AA BAB|B| A BAB|AB|BA|B| B 00| B 00去掉A , 去掉A BS0 A S0 AA BAB|AB|BA|B|BB A BAB|AB|BA|00|BBB 00 B 00去掉S0 A, 添加新变元S0 BAB|AB|BA|00|BB S

9、0 VB|AB|BA|UU|BBA BAB|AB|BA|00|BB A VB|AB|BA|UU|BBB 00 B UU V BA U 0问题3.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭。a.A B方法一：CFG。设有CFG G1(Q1, ,R1,S1)和G2=(Q2, ,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q, ,R,S0)，其中Q= Q1 Q2 S0, S0是起始变元，R= R1 R2 S0 S1|S2.方法二：PDA。设P1=(Q1, , 1, 1,q1,F1)识别A，P2=(Q1, , 2, 2,q2,F2)是识别B。则如下构造的P=(Q

10、, , , ,q0,F)识别A B，其中1)Q=Q1 Q2 q0是状态集，2) 1 2，是栈字母表，3)q0是起始状态，4)FF1 F2是接受状态集，5) 是转移函数，满足对任意q Q, a ,b (q,a,b)=b.连接AB方法一：CFG。设有CFG G1(Q1, ,R1,S1)和G2=(Q2, ,R2,S2)且L(G1)=A, L(G2)=B。构造CFG G=(Q, ,R,S0)，其中Q= Q1 Q2 S0, S0是起始变元，R= R1 R2 S0 S1S2.方法二：PDA。设P1=(Q1, , 1, 1,q1,F1)识别A，P2=(Q1, , 2, 2,q2,F2)是识别B，而且P1满足

11、在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q, , , ,q1,F)识别A B，其中1)Q=Q1 Q2是状态集，2) 1 2，是栈字母表，3)q1是起始状态，4)FF1 F2是接受状态集，5) 是转移函数，满足对任意q Q, a ,b (q,a,b)=c.A*方法一：CFG。设有CFG G1(Q1, ,R1,S1)，L(G1)=A。构造CFG G=(Q, ,R,S0)，其中Q= Q1 S0, S0是起始变元，R= R1 S0 S0S0|S1| .方法二：PDA。设P1=(Q1, , 1, 1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，

12、则栈中为空)这个要求。则如下构造的P=(Q, , , ,q1,F)识别A*，其中1)Q=Q1 q0是状态集，2) 1，是栈字母表，3)q0是起始状态，4)FF1 q0是接受状态集，5) 是转移函数，满足对任意q Q, a ,b (q,a,b)=3.16 先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题3.15的结果，给出每一个正则语言都是上下文无关文法的一个证明。解：设有正则表达式T，将其转化为上下文无关文法。1)首先添加S T，且令S为起始变元。2)根据T的不同形式，按如下方式添加规则1若Ta ， 则在规则集中添加T a,2若T ， 则在规则集中添加T ,3若T ， 则在规

13、则集中添加T T，4若TA B， 则在规则集中添加T A|B， 5若TAB, 则在规则集中添加T AB，6若TA*, 则在规则集中添加T A,和A AA| 3) 若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。下面来证明每一个正则语言都是上下文无关的 由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。3.17 a. 设C是上下文无关语言，R是正则语言。证明语言C R是上下文无关的。b利用a证明语言A

14、=w | w a,b,c*, 且含有数目相同的a,b,c证明：a. 设P=(Q1, , , 1,q1,F1)是一个识别C的PDA，N=(Q2, , 2,q2,F2)是识别R的一台NFA。下面构造识别C R的PDA如下S=(Q, , , ,q0,F):1)Q=Q1Q2, 是状态集，2)q0=(q1,q2)是起始状态，3)F= F1F2, 是接受状态集，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. A a*b*c*=anbncn|n 0, 若A是上下文无关的，则由a中命题知anbn

15、cn|n 0也是上下文无关的，矛盾。3.18 用泵引理证明下述语言不是上下文无关的：a.0n1n0n1n | n 0假设语言上下文无关，设p为泵长度，取S=0p1p0p1p.由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy,首先，它一定横跨S的中点，否则，若vxy位于S的前半段，由于|vxy| p, 则uv2xy2z中1将是后半段字符串的第一个字符，即不可能是0n1n0n1n的形式。同理，vxy也不可能位于S后半段的位置上。但是,若vxy跨越S的中点时，将S抽取成uxz，它形如0p1i0j1p,i，j不可能都为p，即uxz不可能是0n1n0n1n的形式。综上，可知S不能被抽取

16、，因此，该语言不是上下文无关的。b. 0n#02n#03n | n 0假设语言上下文无关，设p为泵长度，取S=0p#02p#03p, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。考察子串vxy。首先，v,y中不能有#，否则S抽取成uxz后，其中#个数 1。由条件3，vxy或者位于第2个#之前，或者位于第1个#之后。下面讨论这两种情况：1此时，uv2xy2z中第3部分0的个数保持不变，而前面部分的0的个数至少有一个增加，因此，uv2xy2z不在该语言中。2此时，uv2xy2z中第1部分0的个数保持不变，而第2，3部分0的个数至少有一个增加，也有uv2xy2z不在该语言中。因此，该语言不是

17、上下文无关的。c. w#x | w,x a,b*, w是x的子串假设该语言上下文无关，设p为泵长度，取S=0p1p#0p1p, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。现在假设# x，则必存在不全为0的i,j，使得vy=1i0j，下面分两种情况考虑：1j 0, 则uxz=0p1p-i#0p-j1p不在该语言中2j=0, 则uv2xy2z中#左侧的字符串长度大于右

18、边，不在该语言中。因此，该语言不是上下文无关的。d. x1#x2# #xk | k 2, 每一个xi a,b*, 且存在xixj假设该语言上下文无关，设p为泵长度，取S=apbp#apbp, 由泵引理知，S可以划分为uvxyz且满足泵引理条件。显然，v,y中不包含#，不然抽取后的S=uxz中将不含#从而不在该语言中。子串vxy不能落在#的左侧，否则uv2xy2z中#左侧的字符串长度将大于右边。子串vxy不能落在#的右侧，否则uxz中#左侧的字符串长度也会大于右边。于是vxy跨越#两侧.此时，S经抽取成uxz后，具有apbi#ajbp的形式，其中，i,j不全为p。因此，uxz不在该语言中。综上该

19、语言不是上下文无关的。3.19 证明：设G是一个Chomsky范式CFG，则对任一长度 2的字符串w L(G), w的任何派生恰好有2n1步。证明：(用数学归纳法)当n=2时，对于Chomsky范式CFG，长度为2的字符串必由3步派生，此时命题为真。假设当2 n k时命题为真。当n=k+1时，对于长度为k+1的字符串s=s1s2 sk+1，存在S0的一个直接派生S0 AB，使得A产生子串s1s2 sp，B产生子串sp+1sp+2 sk+1，其中1 p k+1。由归纳假设，A产生子串s1s2 sp需要2p-1步派生，而B产生子串sp+1sp+2 sk+1需要2(k+1-p)-1步派生。因此，S0

20、产生字符串s共需2(k+1)-1步派生。即当n=k+1时命题亦真。因此，由G产生长度为n 2的字符串需要2n-1派生。3.20 设G是一个含有b个变元的乔姆斯基范式CFG。证明：如果G产生某个字符串使用了至少2b步的派生，则L(G)是无穷的。证明：设G产生字符串S需要至少2b步。由于一个分支点(变元)对应一次派生，所以S的语法树至少有2b个分支点。又由于在乔姆斯基范式下，一个分支点至多有两个子分支点(这意味着层数 n的结点个数 2b1)，从而的由分支点组成的子树的高度大于等于b+1。有一条路径上分支点(变元)个数 b+1。由鸽巢原理：必有某个变元R在该路径上出现至少两次。不妨假设R出现在路径上

21、最下面的b+1个变元中。按上图所示，将S划分为uvxyz，在每一个R的下面有一棵子树，它产生S的一部分。上面的R有一棵较大的子树，产生vxy，下面的R有一棵较大的子树，产生x，由于这两棵子树由同一个变元产生，因而可以相互替换。这里采用如下操作：反复用较大子树去替换较小子树，则我们得到对于任意n1, uv nxy nz L(G)。所以若我们能证明v,y不全为，则L(G)是无穷的。事实上，由乔姆斯基范式的特点，上面一个R的派生选择的必为R AB形式的规则，而且不可能有A 和B ，所以v,y不全为 。从而命题得证。3.22 考虑语言B=L(G), 其中G是练习3.13中给出的文法。定理3.19关于上

22、下文无关语的泵引理称存在关于B的泵长度p。p的最小值等于多少？要求给出证明。证明：p的最小值为4。令D=0i#0j#0k | i, j, k 0, E=0i#02i | i 0, 则L(G)=D E。L(G)中长度为1的字符串仅有#,不能被抽取。L(G)中长度为2的字符串仅有#,也不能被抽取。D中长度 3的字符串必含有0，所以一定可以被抽取。E中长度 3的字符串也可以被抽取(E中没有长度等于3的字符串)。只需令uvxyz分别为v=0,x=#,y=00, u,z为两边其余的字符串即可。注意到此时|vxy|4。但是泵长度不能等于3。因为若p=3，则要求|vxy| 3，但是对于E中的字符串来说，每在

23、#左边抽取1个0，则同时必须在#右边抽取2个0，即|vy| 3，又x必须包含#, 所以任何有效的抽取必有|vxy| 4。综上所述，p的最小值为4。3.23 给出一个语言，它不是上下文无关的、但满足泵引理的三个条件。要求给出证明。解：令Aaibjckdl | i,j,k,l 0, 且当i=1时，j=k=l，则：(1)A满足泵引理的三个条件。取泵长度p1。对A中任意长度大于1的字符串s= aibjckdl ，分情况可以如下抽取：若i=1,则j=k=l, 取v=a,uxy= ，z= bjcjdj, 则对 n 0，uvnxynz= aibjcjdj A；若i 2，且j,k,l不同时为0，不妨设j 0，

24、取u=ai,v=b,xy= ，z= bj-1ckdl, 则对 n 0，uvnxynz= aibj-1+nckdl A；若i 2，且j=k=l=0, 取u=ai-1,v=a,xyz= , 则对 n 0，uvnxynz= ai-1+n A；若i=0，则j,k,l不同时为0，不妨设j 0，取v=b,uxy= ，z= bj-1ckdl, 则对 n 0，uvnxynz=bj-1+nckdl A。(2) A不是上下文无关语言。事实上，若A为上下文无关语言，另取正则语言R=ab*c*d*，由问题3.17可知，L R是上下文无关的。但这与L R=abncndn | n 0不是一个上下文无关语言矛盾。因此，A不是上下文无关的。