2.4和2.5 给出产生下述语言的上下文无关文法和PDA，其中字母表?={0,1}。
a. {w | w至少含有3个1}
S→A1A1A1A A→0A|1A|?
b. {w | w以相同的符号开始和结束}
S→0A0|1A1 A→0A|1A|?
c. {w | w的长度为奇数}
S→0A|1A A→0B|1B|? B→0A|1A
d. {w | w的长度为奇数且正中间的符号为0}
S→0S0|1S1|0S1|1S0|0
e. {w | w中1比0多}
S→A1A
A→0A1|1A0|1A|AA|?
?,??$ 1,0?? 0,1?? 0,??0 1,??1 ?,1?? ?,??$ 0,??? ?,$?? 0,??0 1,??0 0,0?? 1,0?? 0,??? 1,??? 0,??? 1,???
0,??? 1,??? 0,??0 0,0?? 1,??1 1,1?? 0, ??? 1, ??1 ?,1?? ?,1?? ?,1?? ?,1?? ?,$?? f. {w | w=wR}
S→0S0|1S1|1|0 g. 空集
S→S
2.15 用定理2.6中给出的过程，把下述CFG转换成等价的乔姆斯基范式文法。
A?BAB|B|? B?00|?
解：添加新起始变元S0,
S0?A
去掉B?? S0?A
0,??0 0,0?? 1,??1 1,1?? 1,??? ?,??$ 0,??? ?,$?? ?,??? A?BAB|B|? B?00|?
A?BAB|AB|BA|B|?
B?00
去掉A??, S0?A
去掉A?B S0?A
A?BAB|AB|BA|B|BB B?00
去掉S0?A,
A?BAB|AB|BA|00|BB
B?00
添加新变元 S0?VB|AB|BA|UU|BB A?VB|AB|BA|UU|BB B?UU V?BA U?0
S0?BAB|AB|BA|00|BB A?BAB|AB|BA|00|BB B?00
3.15 证明可判定语言类在下列运算下封闭。
a. 并。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：
M＝“输入w，
1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中有一个接受，则接受。
若都拒绝，则拒绝。”
M为识别A1?A2的判定器。所以可判定语言类对并运算封闭。 b. 连接。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：
M＝“输入w，
1) 列出所有将w分成两段的方式(|w|+1种).
2) 对于每一种分段方式，在第一段上运行M1，在第二段上运行M2。
若都接受，则接受。
3) 若没有一种分段方式被接受则拒绝。”
M为识别A1?A2的判定器。所以可判定语言类对连接运算封闭。 c. 星号。
证明：设M1为识别可判定语言A的判定器。
M＝“输入w，
1) 列出w的所有分段的方式(2|w|-1种)。 2) 对于每一种分段方式，重复下列步骤：
3) 分别在每一段上运行M1，若每一段都能被M1接受，则接受。 4) 若没有一种分段方式被接受则拒绝。”
M为识别A*的判定器。所以可判定语言类对星号运算封闭。 d. 补。
证明：设M1=(Q,?,?,?,q0, q1, q2)为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。令M=(Q,?,?,?,q0, q2, q1)，其中q2为接受状态，q1为拒绝状态。则M为识别A的判定器。所以可判定语言类对补运算是封闭的。
e. 交。
证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：
M＝“输入w，
1) 分别在w上运行M1和M2，每运行一步M1就运行一步M2。 2) 若M1和M2中都接受，则接受。
若M1和M2中有一个拒绝，则拒绝。”
M为识别A1?A2的判定器。所以可判定语言类对交运算是封闭的。
3.16 证明图灵可识别语言类在下列运算下封闭： a．并 b．连接 c．星号 d．交
证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设A和B是图灵可识别语言，A=L(M1)，B=L(M2)，M1和M2是两个图灵机。 a．并
M=“对于输入w：
1) 在输入w上并行运行M1和M2；
2) M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。” M识别A1?A2。所以图灵可识别语言类对并运算是封闭的。 b. 连接 M＝“输入w，
1) 出所有将w分成两段的方式(|w|+1种). 2) 对于i=1,2,?重复以下步骤：
3) 对于每一种分段方式，在第一段上运行M1i步，在第二段上运行M2 i
步，或者直到停机。若都接受，则接受。”
M识别A1?A2。所以图灵可识别语言类对连接运算是封闭的。 c．星号 M＝“输入w，
1) 列出w的所有分段的方式(2|w|-1种). 2) 对于i=1,2,?重复以下步骤：
3) 对于每一种分段方式，分别在每一段上运行M1 i步，或者直到停机。