可计算性与计算复杂性计算原理答案.doc

由天下分享时间：2025/1/5 3:19:06 加入收藏我要投稿点赞

1.6 画出识别下述语言的DFA的状态图。

a){w | w从1开始以0结束}

0 1 0,1 1 1 0

0 b){w | w至少有3个1}

c) {w | w含有子串0101}

1 1 0 0 1 0 0 1 0,1 0 1 0 1 0 1 0,1 d) {w | w的长度不小于3，且第三个符号为0}

0,1 0,1 1 0,1 0 1 0 0,1 e) {w | w从0开始且为奇长度，或从1开始且为偶长度}

0 1 0,1 0,1 0,1 0,1 0 或

1 0,1 0,1

word文档可编辑

f) {w | w不含子串110}

0 1 1 0 0,1 g) {w | w的长度不超过5}

h){w | w是除11和111以外的任何字符} 1 1 1

i){w | w的奇位置均为1}

j) {w | w至少含有2个0，且至多含有1个1}

0 k) {ε,0}

0 1

word文档可编辑

0,1 0,1 0,1 0,1 0,1 0,1 0,1 0 0 0 0,1 0 0,1 0,1 1 0 1 0 1 0 0 0 1 1 1 0,1

0,1 0,1 l) {w | w含有偶数个0，或恰好两个1}

m) 空集 n) 除空串外的所有字符串

1.29利用泵引理证明下述语言不是正则的。 a. A1={012| n?0}。

证明：假设A1是正则的。设p是泵引理给出的关于A1的泵长度。

令S=012,

∵S是A1的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含0，xyyz中，0比1、2多，xyyz不是A1的成员。违反泵引理的条件1，矛盾。 ∴A1不是正则的。

b. A2={www | w?{a,b}*}.

证明：假设A2是正则的。设p是泵引理给出的关于A2的泵长度。

令S=ababab,

∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。根据条件3，y中只含a，所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz不是A2的成员。违反泵引理的条件1，矛盾。 ∴A2不是正则的。

ppp

nnn

1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0,1 0,1 0,1 word文档可编辑

c. A3={a | n?0}.(在这里，a表示一串2个a .)

证明：假设A3是正则的。设p是泵引理给出的关于A3的泵长度。

令S= a2，

∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。即对任意的i?0，xyiz都应在A3中，且xyiz与xyi+1z的长度都应是2的幂. 而且xyi+1z的长度应是xyiz的长度的2倍(n?1)。于是可以选择足够大的i，使得|xyiz|=2>p. 但是|xyz|-|xyz|=|y|?p. 即|xyz|<2, 矛盾。 ∴A3不是正则的。 1.46 证明：

a) 假设{010|m,n≥0}是正则的，p是由泵引理给出的泵长度。取s＝010，q>0。

由泵引理条件3知，|xy|≤p，故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语言，这与泵引理矛盾。所以该语言不是正则的。

b) 假设{0n1n|n≥0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n|n≥0}是正则的，这与已知矛盾，故假设不成立。所以该语言不是正则的。

c) 记c={0m1n|m≠n}，┐c为c的补集，┐c∩0*1*={0n1n|n≥0}，已知{0n1n|n≥0}不是正则的。若 ┐c是正则的，由于0*1*是正则的，那么┐c∩0*1*也应为正则的。这与已知矛盾，所以 ┐c不是正则的。由正则语言在补运算下的封闭性可知c也不是正则的。

d) {w | w?{0,1}*不是一个回文}的补集是{w | w?{0,1}*是一个回文}，设其是正则的，令p是由泵引理给出的泵长度。取字符串s=010，显然s是一个回文且长度大于p。由泵引理条件3知|xy|≤p，故y只能由0组成。而xyyz不再是一个回文，这与泵引理矛盾。所以{w | w?{0,1}*是一个回文}不是正则的。由正则语言在补运算下的封闭性可知{w | w?{0,1}*不是一个回文}也不是正则的。

word文档可编辑

pqp

nmn

pqp

i+1

n+1

2n2n

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|?