发布时间 : 星期三 文章可计算性与计算复杂性（计算原理答案）更新完毕开始阅读f72c4220bcd126fff7050ba0
1.6 画出识别下述语言的DFA的状态图。
a){w | w从1开始以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 0 1 0,1 1 1 0
0 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
f) {w | w不含子串110}
0
1
0 1 1 0 0,1 g) {w | w的长度不超过5}
h){w | w是除11和111以外的任何字符} 1 1 1
i){w | w的奇位置均为1}
1
0,1 0
j) {w | w至少含有2个0，且至多含有1个1}
0 k) {ε,0}
0 1
0,1 0,1 0 1 0 0 1 0 1 1 0 1 1 0,1
0,1 0 0 0 0,1 0,1 0,1 0,1 0,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不是正则的。
p
p
p
pp
p
nn
n
1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0,1 0,1 0,1 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. 但是|xyi+1z|-|xyiz|=|y|?p. 即|xyi+1z|<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}不是一个回文}也不是正则的。
**
pq
p
n
mn
pq
p
n+1
n
n
p
2n2n
n