可计算性与计算复杂性(计算原理答案)

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

联系客服:779662525#qq.com(#替换为@)