第 1 章练习与详细解答

教材习题状态
第 1 章在本中文版本中没有像第 2 章那样设置独立的编号习题小节；PDF p.36 是“小结”，p.37 是“参考文献”，随后 PDF p.38 进入第 2 章。因此本文件不伪造 textbook exercise numbering。下面全部标记为 Self-check C1-*，属于为学习与复习编写的补充练习。

1 Self-check C1-1：状态应该记住什么？

某门禁系统每次读取一张卡。如果连续两次读取到同一张卡号，就报警；否则继续工作。

问题： 如果只考虑“是否应该在当前读卡后报警”，状态至少需要保存什么信息？

1.1 Key idea

状态应该保存“影响下一步行为所需的历史摘要”，而不是保存所有历史。

1.2 Detailed solution

为了判断下一张卡是否与上一张相同，系统至少需要知道：

是否还没有读过任何卡；
如果已经读过，上一张卡的卡号是什么。

因此状态并不只是一个固定的有限二值变量；如果卡号取值空间很大，完整系统的状态空间也会相应增大。这个例子用来提醒：

“有限状态自动机”要求状态集合有限，而“任何有状态程序”并不自动等于有限状态自动机。

2 Self-check C1-2：区分三个空对象

判断下列等式是否成立：

\(\varepsilon=\varnothing\)
\(\{\varepsilon\}=\varnothing\)
\(|\varepsilon|=0\)
\(|\{\varepsilon\}|=1\)

2.1 Solution

错。\(\varepsilon\) 是串，\(\varnothing\) 是集合。
错。\(\{\varepsilon\}\) 含一个元素；\(\varnothing\) 不含元素。
对。空串长度为 0。
对。这里竖线表示集合基数时，\(\{\varepsilon\}\) 的元素个数为 1。

最后一条也说明：符号 \(|\cdot|\) 的具体含义依赖对象类型。对串表示长度，对有限集合表示基数。

3 Self-check C1-3：串联接

设 \(x=01\)，\(y=10\)，\(z=1\)。计算：

\(xy\)
\(yx\)
\((xy)z\)
\(x(yz)\)
\(|xyz|\)

3.1 Solution

\[ xy=0110, \qquad yx=1001. \]

所以联接一般不交换。

并且

\[ (xy)z=01101, \qquad x(yz)=01101. \]

验证了结合律。

长度为

\[ |xyz|=|x|+|y|+|z|=2+2+1=5. \]

4 Self-check C1-4：\(\Sigma^k\)、\(\Sigma^*\)、\(\Sigma^+\)

设 \(\Sigma=\{0,1\}\)。

写出 \(\Sigma^0\)。
写出 \(\Sigma^2\)。
\(\varepsilon\in\Sigma^*\) 吗？
\(\varepsilon\in\Sigma^+\) 吗？

4.1 Solution

\[ \Sigma^0=\{\varepsilon\}. \]

\[ \Sigma^2=\{00,01,10,11\}. \]

因为

\[ \Sigma^*=\bigcup_{k\ge0}\Sigma^k, \]

所以 \(\varepsilon\in\Sigma^*\)。

而

\[ \Sigma^+=\bigcup_{k\ge1}\Sigma^k, \]

因此 \(\varepsilon\notin\Sigma^+\)。

5 Self-check C1-5：语言成员性

设

\[ L=\{0^n1^n:n\ge0\}. \]

判断下列串是否属于 \(L\)：

\[ \varepsilon,\quad 01,\quad 0011,\quad 00111,\quad 0101. \]

5.1 Solution

\(\varepsilon\in L\)：取 \(n=0\)。
\(01\in L\)：取 \(n=1\)。
\(0011\in L\)：取 \(n=2\)。
\(00111\notin L\)：0 有 2 个，1 有 3 个。
\(0101\notin L\)：虽然 0 和 1 数量相等，但格式不是“所有 0 在前、所有 1 在后”。

这说明定义语言时，“计数条件”和“顺序条件”必须同时看。

6 Self-check C1-6：双包含证明

证明：对任意集合 \(A,B\)，

\[ A\cap B=B\cap A. \]

6.1 Key idea

证明集合相等，用双包含。

6.2 Detailed solution

先证

\[ A\cap B\subseteq B\cap A. \]

任取 \(x\in A\cap B\)。根据交集定义，\(x\in A\) 且 \(x\in B\)。于是同样有 \(x\in B\) 且 \(x\in A\)，因此 \(x\in B\cap A\)。

反过来，任取 \(x\in B\cap A\)，同理可得 \(x\in A\cap B\)。

所以

\[ A\cap B=B\cap A. \]

7 Self-check C1-7：用逆否命题证明

证明：若整数 \(n^2\) 是偶数，则 \(n\) 是偶数。

7.1 Solution

证明逆否命题：若 \(n\) 是奇数，则 \(n^2\) 是奇数。

设

\[ n=2k+1. \]

则

\[ \begin{aligned} n^2 &=(2k+1)^2\\ &=4k^2+4k+1\\ &=2(2k^2+2k)+1. \end{aligned} \]

因此 \(n^2\) 为奇数。逆否命题成立，所以原命题成立。

8 Self-check C1-8：找反例

命题：如果 \(ab\) 是偶数，那么 \(a\) 和 \(b\) 都是偶数。

判断真假。如果为假，给出反例。

8.1 Solution

命题为假。

取

\[ a=2,\qquad b=3. \]

则

\[ ab=6 \]

是偶数，但 \(b=3\) 不是偶数。

一个反例已经足以推翻全称命题。

正确的相关命题是：如果 \(ab\) 为偶数，则 \(a,b\) 中至少一个为偶数。

9 Self-check C1-9：归纳证明奇数和

证明对所有 \(n\ge1\)，

\[ 1+3+5+\cdots+(2n-1)=n^2. \]

9.1 Solution

9.1.1 基础步骤

\(n=1\) 时：

\[ 1=1^2. \]

成立。

9.1.2 归纳假设

假设对某个 \(k\ge1\)，

\[ 1+3+\cdots+(2k-1)=k^2. \]

9.1.3 归纳步骤

加入下一个奇数 \(2(k+1)-1=2k+1\)：

\[ \begin{aligned} 1+3+\cdots+(2k-1)+(2k+1) &=k^2+2k+1\\ &=(k+1)^2. \end{aligned} \]

所以命题对 \(k+1\) 成立。由数学归纳法，命题对所有 \(n\ge1\) 成立。

10 Self-check C1-10：归纳证明指数最终超过平方

证明对所有 \(n\ge5\)，

\[ 2^n>n^2. \]

10.1 Solution

10.1.1 基础步骤

\[ 2^5=32>25=5^2. \]

10.1.2 归纳假设

假设 \(2^k>k^2\)，其中 \(k\ge5\)。

10.1.3 归纳步骤

\[ 2^{k+1}=2\cdot2^k>2k^2. \]

而当 \(k\ge5\) 时，

\[ 2k^2-(k+1)^2 =k^2-2k-1>0. \]

故

\[ 2k^2>(k+1)^2. \]

于是

\[ 2^{k+1}>(k+1)^2. \]

命题成立。

11 Self-check C1-11：结构归纳

递归定义算术表达式集合 \(E\)：

任意数字 \(d\in\{0,1,\dots,9\}\) 属于 \(E\)；
若 \(x,y\in E\)，则 \((x+y)\in E\)；
若 \(x,y\in E\)，则 \((x\times y)\in E\)。

证明：每个表达式中的左括号数等于右括号数。

11.1 Solution

用结构归纳。

11.1.1 基础结构

单个数字 \(d\) 没有括号，因此左右括号数都为 0，相等。

11.1.2 加法构造

假设 \(x,y\) 各自左右括号数相等。

构造 \((x+y)\) 时，在外层新增加一个左括号和一个右括号，因此总数仍相等。

11.1.3 乘法构造

同理，构造 \((x\times y)\) 时也只新增一对匹配括号，因此左右括号数仍相等。

因为所有 \(E\) 中的表达式都由这三类规则生成，结论对所有表达式成立。

12 Self-check C1-12：把判定问题写成语言

问题：给定一个二进制整数，判断它是否为偶数。

请把这个问题写成语言。

12.1 Solution

取字母表

\[ \Sigma=\{0,1\}. \]

若采用无前导零的标准二进制表示（数字 0 单独允许），则 YES 实例构成语言

\[ L_{\text{even}} =\{0\}\cup\{w0:w\in\{0,1\}^*,\ w\text{ 的首位为 }1\}. \]

如果允许前导零，则可更简单地写成

\[ L_{\text{even}} =\{w\in\{0,1\}^+: w\text{ 最后一位是 }0\}. \]

这里出现了一个很重要的形式化习惯：

在把现实问题写成语言之前，必须先说清楚“输入编码是否合法”。

13 复习建议

如果这些题中以下任一类仍不熟，建议不要急着进入第 2 章：

C1-2 到 C1-5：形式语言基本符号；
C1-6 到 C1-8：证明策略；
C1-9 到 C1-11：归纳；
C1-12：问题与语言的对应。