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步，或者直到停机。