资源描述：
《计算理论习题答案CHAP2new.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2.2a.利用语言A={ambncn
2、m,n³0}和A={anbncm
3、m,n³0}以及例3.20，证明上下文无关语言在交的运算下不封闭。b.利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。证明：a.先说明A,B均为上下文无关文法，对A构造CFGC1S®aS
4、T
5、eT®bTc
6、e对B,构造CFGC2S®Sc
7、R
8、eR®aRb由此知A,B均为上下文无关语言。但是由例3.20,A∩B={anbncn
9、n³0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。b.用反证法。假设CFL在补运算下封闭，则对于
10、(a)中上下文无关语言A,B，,也为CFL，且CFL对并运算封闭，所以也为CFL，进而知道为CFL，由DeMorgan定律＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。2.4和2.5给出产生下述语言的上下文无关文法和PDA，其中字母表S={0,1}。a.{w
11、w至少含有3个1}S→A1A1A1AA→0A
12、1A
13、ee,1®e1,e®10,e®ee,1®ee,1®ea.{w
14、w以相同的符号开始和结束}S→0A0
15、1A1A→0A
16、1A
17、e1,e®11,e®e0,e®e0,e®01,1®e0,0®eb.{w
18、w的长度为
19、奇数}S→0A
20、1AA→0B
21、1B
22、eB→0A
23、1A1,e®e0,e®e1,e®e0,e®ec.{w
24、w的长度为奇数且正中间的符号为0}S→0S0
25、1S1
26、0S1
27、1S0
28、01,e®00,e®e0,e®01,0®e0,0®ee,e®$e,$®ed.{w
29、w中1比0多}S→A1AA→0A1
30、1A0
31、1A
32、AA
33、e1,e®1e,1®e0,e®0e,1®ee,e®$e,$®e1,0®e0,1®ea.{w
34、w=wR}S→0S0
35、1S1
36、1
37、01,e®10,e®e0,e®01,1®e0,0®ee,e®$e,$®e1,e®ee,e®eb.空集S→S2.6
38、给出产生下述语言的上下文无关文法：a．字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。S→bSaSaS
39、aSbSaS
40、aSaSbS
41、eb．语言{anbn
42、n³0}的补集。见问题3.25中的CFG:S→aSb
43、bY
44、TaT→aT
45、bT
46、ec．{w#x
47、w,xÎ{0,1}*且wR是x的子串}。S→UVU→0U0
48、1U1
49、WW→W1
50、W0
51、#V→0V
52、1V
53、ed．{x1#x2#¼#xk
54、k³1,每一个xiÎ{a,b}*,且存在i和j使得xi＝xjR}。S→UVWU→A
55、eA→aA
56、bA
57、#A
58、#V→aVa
59、bVb
60、#B
61、#B→aB
62、
63、bB
64、#B
65、#W→B
66、e2.8证明上下文无关语言类在并,连接和星号三种正则运算下封闭。a.AÈB方法一：CFG。设有CFGG1＝(Q1,S,R1,S1)和G2=(Q2,S,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(Q,S,R,S0)，其中Q=Q1ÈQ2È{S0},S0是起始变元，R=R1ÈR2È{S0®S1
67、S2}.方法二：PDA。设P1=(Q1,S,G1,d1,q1,F1)识别A，P2=(Q1,S,G2,d2,q2,F2)是识别B。则如下构造的P=(Q,S,G,d,q0,F)识别AÈB，其中1)Q=Q1ÈQ2È{q0}
68、是状态集，2)G＝G1ÈG2，是栈字母表，3)q0是起始状态，4)F＝F1ÈF2是接受状态集，5)d是转移函数，满足对任意qÎQ,aÎSe,bÎGed(q,a,b)=b.连接AB方法一：CFG。设有CFGG1＝(Q1,S,R1,S1)和G2=(Q2,S,R2,S2)且L(G1)=A,L(G2)=B。构造CFGG=(Q,S,R,S0)，其中Q=Q1ÈQ2È{S0},S0是起始变元，R=R1ÈR2È{S0®S1S2}.方法二：PDA。设P1=(Q1,S,G1,d1,q1,F1)识别A，P2=(Q1,S,G2,d2,q2,F2)是识别B，而且P1满
69、足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,S,G,d,q1,F)识别AÈB，其中1)Q=Q1ÈQ2是状态集，2)G＝G1ÈG2，是栈字母表，3)q1是起始状态，4)F＝F1ÈF2是接受状态集，5)d是转移函数，满足对任意qÎQ,aÎSe,bÎGed(q,a,b)=a.A*方法一：CFG。设有CFGG1＝(Q1,S,R1,S1)，L(G1)=A。构造CFGG=(Q,S,R,S0)，其中Q=Q1È{S0},S0是起始变元，R=R1È{S0®S0S0
70、S1
71、e}.方法二：PDA。设P1=(Q1,S,G1,d1
72、,q1,F1)识别A，而且P1满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。则如下构造的P=(Q,S,G,d,q1,F)识别A*，其中1)Q=Q1È
