发布时间 : 星期三 文章2、正则语言练习更新完毕开始阅读98da486825c52cc58bd6beac
字符串不可能被枚举出来。
这个思想和定理4.10中的“宽度优先”的策略类似。
4.7 下面描述的不是一个合法的图灵机，解释为什么。
Mbad=“输入是变元x1，x2，…，xk上的一个多项式p：
1) 让x1，x2，。。。，xk取所有可能的整数值。 2) 对所有这些值求p的值。
3) 只要某个取值使得p为0，则接受，否则拒绝”
答：因为图灵机的一个本质要求是一步只能做有限的工作。参考希尔伯特问题一节中图灵机M1的定义。
4.8 下面的语言都是字母表{0，1}上的语言，以实现水平的描述给出判定这些语言的图灵机： a. {w|w包含相同个数的0和1}
b. {w|w所包含的0的个数是1的个数的二倍} c.
{w|w所包含的0的个数不是1的个数的二倍}
答：构造具有3条带的图灵机。第一条带子是输入带，第二条带子存放输入串所包含的0，第三条带子存放输入串所包含的1。 对于问题a.
M1=“对于输入字符串w：
1) 扫描输入，读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空白符为
止。
2) 第2、3条带的读写头回到最左端。
3) 读第2、3条带，每次读一个字符，如果同时读出空白符，则接收，否则拒绝。” 对于问题b:
M2=“对于输入字符串w：
1) 扫描输入，读到0就把0写入第2条带，读到1就把1写入第3条带，直到读到空白符为
止。
2) 第2、3条带的读写头回到最左端。
3) 每次读带3的一个字符就读带2的两个字符。
4) 如果从带3上读出的字符是1，从带2上读出的两个字符都是0，转第3步。否则，拒绝。
如果从带3上读出的字符是空白，从带2上读出的第一个字符也是空白，就接收，否则拒绝。”
29
对于问题c:
M3=“对于输入字符串w：
1) 运行M2。
2) 如果M2拒绝，则接受；如果M2接受，则拒绝。”
4.18 设多项式c1xn+c2xn-1+…+cnx+cn+1有根x=x0，cmax是ci的最大绝对值。证明
|x0|?(n?1)cmax |c1|证明：
1) 当|x0|?1时，由条件cmax?|c1| 知不等式显然成立。 3) 当|x0|>1时，由
c1x0n?c2x0n?1?...?cnx0?cn?1?0c1x0n??(c2x0n?1?...?cnx0?cn?1)(c2x0n?1?...?cnx0?cn?1)c1x0??x0n?111c1x??(c2?...?cnn?2?cn?1n?1)x0x0取绝对值
|c1||x0|?|c2?...?cn1x0n?2?cn?11x0n?1|11?|c| n?1|x0|n?2|x0|n?1 ?|c2|?...?|cn|?|cn?1| ?|c2|?...?|cn|
最后得到
|c1||x0|?ncmax<(n?1)cmax |x0|?(n?1)cmax |c1|
30
第5章、可判定性习题解答
练习
5.1 对于下图所示的DFA M，回答下列问题，并说明理由。 a.
否，M不接受011。
否，不是ADFA的有效输入编码。
0 1 0 1 0，1
b.
d.
否，M接受串0100。 是，L(M) = L(M)
5.2 考虑DFA和正则表达式是否等价的问题。将这个问题表示为一个语言并证明它可判定。 解：设EQD-R={
F=“对于输入
1) 将正则表达式B转化为等价的DFA C。 2) 判定
5.3 设ALLDFA={ | A是一个识别?*的DFA}。证明ALLDFA可判定。 证明：设计一个判定ALLDFA的TM M即可。
M＝“对于输入，其中A是一个DFA:
31
1) 构造DFA B，使得L(B)= ?*。
2) 判定
5.4 AεCFG={
M=“输入
1) 判定
5.5 设INFINITEDFA={|A是一个DFA，且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。
证明：设计一个判定INFINITEDFA的TM M即可。 M=“对于输入，其中A是一个DFA：
1) 按照引理2.32 证明中的构造方法，把DFA A转换成等价的正则表达式。 2) 扫描正则表达式，如果包含星号运算符*，则接受；否则拒绝。”。
5.6 设X是集合{1，2，3，4，5}，Y是集合{6，7，8，9，10}。以表5-4描述函数
f：X→Y，g：X→Y。
N f(n) g(n) 1 2 3 4 5 a.
6 7 6 7 6 10 9 8 7 6 f 不是一对一的。因为1≠3，但是f(1) = f(3) = 6。g是一对一的。
b. f 不是到上的。因为8∈Y，不存在a∈X，使得f(a) = 8。g是到上的。 c.
f 不是对应的。g是对应的。
32