计算理论课后题及答案2

第三章上下文无关语言3.1略。3.2a.利用语言A={ambncn|m,n0}和A={anbncm|m,n0}以及例3.20，证明上下文无关语言在交的运算下不封闭。b.利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFGC1SaS|T|TbTc|对B,构造CFGC2SSc|R|RaRb由此知A,B均为上下文无关语言。但是由例3.20,A∩B={anbncn|n0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，A,B也为CFL，且CFL对并运算封闭，所以BA也为CFL，进而知道BA为CFL，由DeMorgan定律BA＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。3.3略。3.4和3.5给出产生下述语言的上下文无关文法和PDA，其中字母表={0,1}。a.{w|w至少含有3个1}S→A1A1A1AA→0A|1A|b.{w|w以相同的符号开始和结束}S→0A0|1A1A→0A|1A|c.{w|w的长度为奇数}S→0A|1AA→0B|1B|B→0A|1A,11,10,,1,11,11,0,0,01,10,01,0,1,0,d.{w|w的长度为奇数且正中间的符号为0}S→0S0|1S1|0S1|1S0|0e.{w|w中1比0多}S→A1AA→0A1|1A0|1A|AA|f.{w|w=wR}S→0S0|1S1|1|0g.空集S→S3.6给出产生下述语言的上下文无关文法：a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。S→bSaSaS|aSbSaS|aSaSbS|b．语言{anbn|n0}的补集。见问题3.25中的CFG:S→aSb|bY|TaT→aT|bT|c．{w#x|w,x{0,1}*且wR是x的子串}。S→UVU→0U0|1U1|WW→W1|W0|#V→0V|1V|d．{x1#x2##xk|k1,每一个xi{a,b}*,且存在i和j使得xi＝xjR}。S→UVWU→A|A→aA|bA|#A|#V→aVa|bVb|#B|#B→aB|bB|#B|#W→B|3.7略。1,00,0,01,00,0,$,$1,1,10,0,1,$,$1,00,11,10,0,01,10,0,$,$1,,3.8证明在3.1节开始部分给出的文法G2中，字符串thegirltouchestheboywiththeflower有两个不同的最左派生，叙述这句话的两个不同意思。句子名词短语动词短语复合名词动词短语冠词名词动词短语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_the_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_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有两个非确定性的分支：一个分支先读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,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AS0AABAB|B|ABAB|AB|BA|B|B00|B00去掉A,去掉ABS0AS0AABAB|AB|BA|B|BBABAB|AB|BA|00|BBB00B00去掉S0A,添加新变元S0BAB|AB|BA|00|BBS0VB|AB|BA|UU|BBABAB|AB|BA|00|BBAVB|AB|BA|UU|BBB00BUUVBAU0问题3.15证明上下文无关语言类在并,连接和星号三种正则运算下封闭。a.AB方法一：CFG。设有CFGG1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(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,,,,q0,F)识别AB，其中1)Q=Q1Q2{q0}是状态集，2)＝12，是栈字母表，3)q0是起始状态，4)F＝F1F2是接受状态集，5)是转移函数，满足对任意qQ,a,b(q,a,b)=.,)(,,)(,,,,),,,(),,,()},,(),,{(221102121elsebQqbQqbaqqbaqbaqqq若若若b.连接AB方法一：CFG。设有CFGG1＝(Q1,,R1,S1)和G2=(Q2,,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(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满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,,,,q1,F)识别AB，其中1)Q=Q1Q2是状态集，2)＝12，是栈字母表，3)q1是起始状态，4)F＝F1F2是接受状态集，5)是转移函数，满足对任意qQ,a,b(q,a,b)=.,,)(,),,,(),,(),(,),,,(,,)},,{(),,(,)(,),,,(222111211111elsebQqbaqbaFqbaqbaFqqbaqbFQqbaq若若若若c.A*方法一：CFG。设有CFGG1＝(Q1,,R1,S1)，L(G1)=A。构造CFGG=(Q,,R,S0)，其中Q=Q1{S0},S0是起始变元，R=R1{S0S0S0|S1|}.方法二：PDA。设P1=(Q1,,1,1,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,,,,q1,F)识别A*，其中1)Q=Q1{q0}是状态集，2)＝1，是栈字母表，3)q0是起始状态，4)F＝F1{q0}是接受状态集，5)是转移函数，满足对任意qQ,a,b(q,a,b)=.,,,),(),,(),(,),,,(,,)},,{(),,(,),,,(0111111111elsebaqqqbaFqbaqbaFqqbaqFQqbaq若若若若3.16先说明如何把正则表达式直接转换成等价得上下文无关文法，然后利用问题3.15的结果，给出每一个正则语言都是上下文无关文法的一个证明。解：设有正则表达式T，将其转化为上下文无关文法。1)首先添加ST，且令S为起始变元。2)根据T的不同形式，按如下方式添加规则①．若T＝a，则在规则集中添加Ta,②．若T＝，则在规则集中添加T,③．若T＝，则在规则集中添加TT，④．若T＝AB，则在规则集中添加TA|B，⑤．若T＝A·B,则在规则集中添加TAB，⑥．若T＝A*,则在规则集中添加TA,和AAA|3)若有新添加的变元，则根据其所对应的表达式转第2步，直到没有新的变元出现。下面来证明每一个正则语言都是上下文无关的由正则语言与正则表达式的等价性可知：对于一个正则语言都存在一个描述他的正则表达式，由前述讨论可知，这个正则表达式可转换为一个与之等价的上下文无关的文法。因此，此正则语言能由这个上下文无关文法产生。所以正则语言是上下文无关的。3.17a.设C是上下文无关语言，R是正则语言。证明语言CR是上下文无关的。b．利用a证明语言A={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=Q1×Q2,是状态集，2)q0=(q1,q2)是起始状态，3)F=F1×F2,是接受状态集，4)是转移函数，满足对任意qQ1,rQ2,a,b,((q,r),a,b)={((q’,r’),c)|q’