2.1 略。
2.2 a. 利用语言A={ambncn | m,n?0}和A={anbncm | m,n?0}以及例3.20，证明上下文无关语言在交的运算下不封闭。
b. 利用(a)和DeMorgan律(定理1.10)，证明上下文无关语言在补运算下不封闭。
证明：a.先说明A,B均为上下文无关文法，对A构造CFG C1
S?aS|T|? T?bTc|?
对B,构造CFG C2
S?Sc|R|? R?aRb
由此知 A,B均为上下文无关语言。
但是由例3.20, A∩B={anbncn|n?0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。
b.用反证法。假设CFL在补运算下封闭，则对于(a)中上下文无关语言A,B，A,B也为CFL，且CFL对并运算封闭，所以A?B也为CFL，进而知道A?B为CFL，由DeMorgan定律A?B＝A∩B，由此A∩B是CFL,这与(a)的结论矛盾，所以CFL对补运算不封闭。
2.3 略。
2.4和2.5 给出产生下述语言的上下文无关文法和PDA，其中字母表?={0,1}。
a. {w | w至少含有3个1} 0, ???
S→A1A1A1A 1, ??1 A→0A|1A|?
?,1?? ?,1?? ?,1??
b. {w | w以相同的符号开始和结束}
S→0A0|1A1 0,??? A→0A|1A|? 1,??? 0,??0 0,0??
1,??1 1,1??
c. {w | w的长度为奇数} 0,???
S→0A|1A 1,??? A→0B|1B|? B→0A|1A
0,???
1,???
d. {w | w的长度为奇数且正中间的符号为0}
S→0S0|1S1|0S1|1S0|0
0,??0 0,0??
1,??0 1,0??
?,??$ 0,??? ?,$??
e. {w | w中1比0多} 1,0?? S→A1A
0,1?? A→0A1|1A0|1A|AA|?
0,??0
1,??1 ?,1??
?,??$ ?,1?? ?,$??
f. {w | w=wR}
S→0S0|1S1|1|0 0,??0 0,0??
1,??1 1,1??
1,???
?,??$ 0,??? ?,$?? ?,??? g. 空集
S→S
2.6 给出产生下述语言的上下文无关文法： a． 字母表{a,b}上a的个数是b的个数的两倍的所有字符串组成的集合。 S→bSaSaS|aSbSaS|aSaSbS|?
b．语言{anbn|n?0}的补集。见问题3.25中的CFG: S→aSb|bY|Ta T→aT|bT|?
c．{w#x | w, x?{0,1}*且wR是x的子串}。 S→UV
U→0U0|1U1|W W→W1|W0|# V→0V|1V|?
d．{x1#x2#?#xk|k?1, 每一个xi?{a,b}* , 且存在i和j使得xi＝xjR}。 S→UVW U→A|?
A→aA|bA|#A|# V→aVa|bVb|#B|# B→aB|bB|#B|# W→B|?
2.8 证明上下文无关语言类在并,连接和星号三种正则运算下封闭。
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,?,?,?,q0,F)识别A?B，其中 1) Q=Q1?Q2?{q0}是状态集， 2) ?＝?1??2，是栈字母表， 3) q0是起始状态，
4) F＝F1?F2是接受状态集，
5) ?是转移函数，满足对任意q?Q, a???,b???
?{(q1,?),(q2,?)},若q?q0,a?b??,??(q,a,b),若q?Q,b?(?),?111??(q,a,b)=?
?(q,a,b),若q?Q,b?(?),222????,else.?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满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。 则如下构造的P=(Q,?,?,?,q1,F)识别A?B，其中 1) Q=Q1?Q2是状态集， 2) ?＝?1??2，是栈字母表， 3) q1是起始状态，
4) F＝F1?F2是接受状态集，
5) ?是转移函数，满足对任意q?Q, a???,b???
?1(q,a,b),若q?Q1?F1,b?(?1)?,???(q,a,b)?{(q,?)},若q?F1,a?b??,12???(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),
??2(q,a,b),若q?Q2,b?(?2)?,???,else.?
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满足在接受之前排空栈(即若进入接受状态，则栈中为空)这个要求。
则如下构造的P=(Q,?,?,?,q1,F)识别A*，其中 1) Q=Q1?{q0}是状态集， 2) ?＝?1，是栈字母表，
3) q0是起始状态，
4) F＝F1?{q0}是接受状态集，
5) ?是转移函数，满足对任意q?Q, a???,b???
?1(q,a,b),若q?Q1?F1,???(q,a,b)?{(q,?)},若q?F1,a?b??,11??
?(q,a,b)=??1(q,a,b),若q?F1,(a,b)?(?,?),?(q1,?)若q?q0,a?b??,???,else.?
2.9 证明在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_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 含义是： 女孩用花碰这个男孩
2.10 给出产生语言A={aibjck| i,j,k?0且或者i=j或者j=k}的上下文无关文法。你给出的文法是歧义的吗？为什么？ 解：下面是产生A的一个CFG:
S?UV|AB U?aUb|? V?cV|? A?aA|? B?bUc|?
这个CFG是歧义的，因为字符串abc有如下两种不同的最左派生： S?UV?aUbV?abV?abcV?abc S?AB?aAV?aV?abVc?abc
2.11 给出识别2.10中语言A的下推自动机的非形式描述。 解：其非形式描述为：
此PDA有两个非确定性的分支：一个分支先读a，并且每读一个a将一个a推入栈中，当碰到b时，每读一个b从栈中弹出一个a，若没有a可弹出则拒绝，最后读c且不改变栈中的内容，若此时栈为空则接受。另一个分支也是先读a，但不改变栈中内容，当碰到b时，每读一个b将一个b推入栈中，再读c, 每读一个c从栈中弹出一个b，若没有a可弹出则拒绝，若c读完后栈为空则接受。开始时，读输入串的字符，非确定性的选择一个分支运行，若有一个分支接受则接受，否则拒绝。
2.14 设有上下文无关文法G:
S?TT|U U?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=0#0, 则对于任意划分s=xyz(|xy|?p, |y|>0), xynz=0#0?A,
p
2p
p+i
2p
所以不是正则的。
2.15 用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。