第 2 章 习题与详细解答

Source policy
题号严格沿用教材第 2 章。题意来自 PDF p.48–50、p.58–59、p.62、p.68 的页面图像核验。解答为本项目自行推导。教材用 * / ! / !! 标注的题在本文件中尽量保留其提示性，但不把这些符号解释成统一难度等级。对于依赖机械图几何细节、而扫描页未给出文字化方向约定的习题 2.2.1，本文件明确标出“图像依赖”，不伪造唯一的转移表。

1 1. DFA：教材习题 2.2.1–2.2.11

1.1 习题 2.2.1：滚大理石球玩具【图像依赖】

教材图 2-8 中有入口 A、B，出口 C、D，以及三个会在大理石通过后改变方向的杠杆 \(x_1,x_2,x_3\)。要求：

1. 用有穷自动机建模，A/B 为输入；从 D 出来表示接受，从 C 出来表示不接受；
2. 非形式化描述该自动机的语言；
3. 若杠杆在大理石通过之前改变方向，分析答案如何变化。

1.1.1 解题关键

真正需要保存的历史只有三个杠杆当前的方向。每个杠杆只有两种方向，因此机械内部配置至多有

\[ 2^3=8 \]

种。

若还要让“最后一个球从 D 还是 C 出来”直接对应 DFA 的接受状态，可把最近一次出口也编码到状态中：

\[ Q=\{0,1\}^3\times\{\bot,C,D\}. \]

这里 \(\bot\) 表示尚未投入大理石。

于是最多只有

\[ 8\times 3=24 \]

个状态，显然是有限的。

对每个状态 \((x_1,x_2,x_3,e)\) 和输入 \(A\) 或 \(B\)：

1. 按当前三个杠杆方向沿图 2-8 追踪大理石路径；
2. 记录它经过哪些杠杆；
3. 将经过的杠杆翻转；
4. 记录出口 \(e'\in\{C,D\}\)；
5. 新状态就是 \((x'_1,x'_2,x'_3,e')\)。

接受状态集合：

\[ F=\{(x_1,x_2,x_3,D)\}. \]

1.1.2 为什么本版不写唯一 8/24 状态转移表

扫描图明确画出了杠杆位置和通道，但正文没有把“某一种斜向杠杆姿态到底把来自每个入口方向的球导向哪条分支”写成离散文字规则。若直接从扫描图主观补充这一机械约定，会违反 source fidelity。

因此本版给出严格可执行的有限状态建模方法，但不把未经文字/高质量原图交叉验证的具体路由表冒充教材答案。

1.1.3 (b) 语言的正确抽象描述

在图示初始杠杆配置下，语言是

\[ L=\{w\in\{A,B\}^*\mid \text{处理 }w\text{ 的最后一个大理石从 D 离开}\}. \]

若以后取得更清晰的原版图或教师答案，只需要把上面的机械路由规则补入，即可机械地枚举完整 DFA 并进一步化简语言描述。

1.1.4 (c) “通过前翻转”与“通过后翻转”的区别

状态集合不需要改变，改变的是转移函数：

• 原题：先按旧方向路由，再翻转经过的杠杆；
• 变式：先翻转即将经过的杠杆，再按新方向路由。

因此这是“同一有限状态空间、不同 \(\delta\)”的问题。

---

1.2 习题 2.2.2：扩展转移函数与分割无关

证明：对任意状态 \(q\) 和串 \(x,y\)，

\[ \hat\delta(q,xy) = \hat\delta(\hat\delta(q,x),y). \]

1.2.1 解答

对 \(|y|\) 归纳。

基础情况 \(y=\varepsilon\)：

\[ \hat\delta(q,x\varepsilon)=\hat\delta(q,x) = \hat\delta(\hat\delta(q,x),\varepsilon). \]

归纳假设：对某个 \(y\) 成立：

\[ \hat\delta(q,xy)=\hat\delta(\hat\delta(q,x),y). \]

归纳步：令新串为 \(ya\)，其中 \(a\in\Sigma\)：

\[ \begin{aligned} \hat\delta(q,xya) &=\delta(\hat\delta(q,xy),a)\\ &=\delta(\hat\delta(\hat\delta(q,x),y),a)\\ &=\hat\delta(\hat\delta(q,x),ya). \end{aligned} \]

故命题成立。

---

1.3 习题 2.2.3：把最后一个符号移到前面处理

证明：对任意状态 \(q\)、串 \(x\) 和符号 \(a\)，

\[ \hat\delta(q,ax) = \hat\delta(\delta(q,a),x). \]

1.3.1 解答

直接使用习题 2.2.2，令第一个分段为单字符 \(a\)，第二个分段为 \(x\)：

\[ \hat\delta(q,ax) = \hat\delta(\hat\delta(q,a),x). \]

而单字符情形满足

\[ \hat\delta(q,a)=\delta(q,a), \]

所以

\[ \boxed{\hat\delta(q,ax)=\hat\delta(\delta(q,a),x)}. \]

---

1.4 习题 2.2.4：为三个语言设计 DFA

1.4.1 (a) 所有以 00 结尾的二进制串

用状态记录当前后缀与 00 的匹配程度：

• \(q_0\)：当前不以 0 结尾；
• \(q_1\)：当前恰有一个有用的尾随 0；
• \(q_2\)：当前以 00 结尾。

状态	0	1	接受？
\(q_0\)	\(q_1\)	\(q_0\)	否
\(q_1\)	\(q_2\)	\(q_0\)	否
\(q_2\)	\(q_2\)	\(q_0\)	是

1.4.2 (b) 含有三个连续 0 的串

状态	含义	0	1	接受？
\(q_0\)	尾部连续 0 个数为 0	\(q_1\)	\(q_0\)	否
\(q_1\)	尾部连续 1 个 0	\(q_2\)	\(q_0\)	否
\(q_2\)	尾部连续 2 个 0	\(q_3\)	\(q_0\)	否
\(q_3\)	已经出现 000	\(q_3\)	\(q_3\)	是

1.4.3 (c) 含子串 011

状态	含义	0	1	接受？
\(q_0\)	尚无有效匹配	\(q_1\)	\(q_0\)	否
\(q_1\)	当前后缀为 0	\(q_1\)	\(q_2\)	否
\(q_2\)	当前后缀为 01	\(q_1\)	\(q_3\)	否
\(q_3\)	已见 011	\(q_3\)	\(q_3\)	是

---

1.5 习题 2.2.5：更复杂的 DFA 设计

1.5.1 (a) 任意 5 个连续符号中至少含 2 个 0

最稳妥的设计不是试画几十条边，而是把状态定义为“最近最多 4 个字符”。

令

\[ Q=\{u\in\{0,1\}^{\le4}\mid u\text{ 尚未导致违规}\}\cup\{d\}, \]

其中 \(d\) 是死状态。

对 \(u\neq d\) 和 \(a\in\{0,1\}\)：

1. 形成 \(ua\)；
2. 若 \(|ua|\ge5\) 且最后 5 个字符中的 0 少于 2 个，则转入 \(d\)；
3. 否则只保留 \(ua\) 的最后 4 个字符作为新状态。

所有非死状态都是接受状态。

这个构造完整、有限，而且直接表达了语言条件。

1.5.2 (b) 倒数第 10 个符号是 1

教材题意是：接受所有倒数第 10 个符号为 1的二进制串。因此长度小于 10 的串全部拒绝。

一个直接而完全正确的 DFA 构造是让状态保存“目前读入串的最后至多 10 个符号”。令

\[ Q=\{u\in\{0,1\}^{\le 10}\}. \]

初态为 \(\varepsilon\)。对状态 \(u\) 和新符号 \(a\)：

• 若 \(|u|<10\)，则转到 \(ua\)；
• 若 \(|u|=10\)，则删去 \(u\) 的第一个符号，再把 \(a\) 接到末尾，也就是只保留最新 10 位。

接受状态恰好是所有长度为 10 且首字符为 1 的状态：

\[ F=\{1x\mid x\in\{0,1\}^9\}. \]

为什么正确？输入读完后，状态就是整个输入的最后 10 个符号；其中首字符恰好就是原串的倒数第 10 个符号。

这个构造状态数较多，但非常清楚地展示了 DFA 的有限记忆思想：只需保留一个固定长度的滑动窗口。

1.5.3 (c) 以 01 开头或以 01 结尾

可以把“开头是否已经成功”和“当前后缀是否为 01”组合。

一种 7 状态实现：

• \(s\)：尚未读字符；
• \(a\)：只读了首字符 0；
• \(b\)：只读了首字符 1；
• \(T\)：已经确定以 01 开头，接受汇状态；
• \(r_0\)：开头失败，当前不以 0 结尾；
• \(r_1\)：开头失败，当前以 0 结尾；
• \(r_2\)：开头失败，当前以 01 结尾。

关键转移：

• \(s\xrightarrow0 a,\;s\xrightarrow1 b\)；
• \(a\xrightarrow1 T,\;a\xrightarrow0 r_1\)；
• \(b\xrightarrow0 r_1,\;b\xrightarrow1 r_0\)；
• \(T\) 对 0/1 自环；
• \(r_0:0\to r_1,1\to r_0\)；
• \(r_1:0\to r_1,1\to r_2\)；
• \(r_2:0\to r_1,1\to r_0\)。

接受状态为 \(T,r_2\)。

1.5.4 (d) 0 的个数被 5 整除，1 的个数被 3 整除

使用乘积状态

\[ q_{i,j},\qquad i\in\mathbb Z_5, \quad j\in\mathbb Z_3. \]

含义：

\[ \#0\equiv i\pmod5, \qquad \#1\equiv j\pmod3. \]

转移：

\[ \delta(q_{i,j},0)=q_{i+1\bmod5,j}, \]

\[ \delta(q_{i,j},1)=q_{i,j+1\bmod3}. \]

初始和唯一接受状态都是 \(q_{0,0}\)。总共 15 个状态。

---

1.6 习题 2.2.6：二进制数模 5

1.6.1 (a) 以 1 开头、按通常二进制解释后为 5 的倍数

设置：

• 初始状态 \(s\)；
• 非法前导 0 死状态 \(d\)；
• 余数状态 \(r_0,\dots,r_4\)。

首字符：

\[ \delta(s,1)=r_1, \qquad \delta(s,0)=d. \]

若当前余数是 \(r\)，再读位 \(b\in\{0,1\}\)，新余数是

\[ r'=(2r+b)\bmod5. \]

因此

\[ \delta(r_i,b)=r_{(2i+b)\bmod5}. \]

接受状态只有 \(r_0\)。

1.6.2 (b) 把字符串反过来解释成二进制数，要求被 5 整除

若从左到右读入的第 \(k\) 位在“反向解释”中权重是 \(2^k\)，则需要同时记住：

1. 当前和模 5 的余数 \(r\)；
2. 当前位权 \(2^k\bmod5\)。

因为

\[ 2^k\bmod5 \]

按

\[ 1,2,4,3,1,2,4,3,\dots \]

周期 4 循环，所以只需记 \(k\bmod4\)。

使用 20 个状态

\[ q_{r,t},\qquad r\in\mathbb Z_5, \quad t\in\mathbb Z_4. \]

令

\[ p_t\in\{1,2,4,3\} \]

是对应的 \(2^t\bmod5\)。读入 \(b\) 后：

\[ \delta(q_{r,t},b) = q_{(r+b p_t)\bmod5,\;t+1\bmod4}. \]

初始状态 \(q_{0,0}\)，所有 \(q_{0,t}\) 都接受。

---

1.7 习题 2.2.7：吸收状态的扩展转移

设 \(q_0\) 满足对每个 \(a\in\Sigma\)，

\[ \delta(q_0,a)=q_0. \]

证明对任意 \(w\)，

\[ \hat\delta(q_0,w)=q_0. \]

1.7.1 解答

对 \(|w|\) 归纳。

• \(w=\varepsilon\)：\(\hat\delta(q_0,\varepsilon)=q_0\)。
• 若 \(\hat\delta(q_0,w)=q_0\)，则对任意 \(a\)：

\[ \hat\delta(q_0,wa) = \delta(\hat\delta(q_0,w),a) = \delta(q_0,a) =q_0. \]

得证。

---

1.8 习题 2.2.8：一个所有输入都回到初态的符号

设对 DFA 的每个状态 \(q\) 都有

\[ \delta(q,a)=q_0. \]

1.8.1 (a) 证明 \(\hat\delta(q,a^n)=q_0\)，\(n>0\)

第一步读入 \(a\) 后就到 \(q_0\)。之后每个 \(a\) 又把 \(q_0\) 映回 \(q_0\)。形式化地对 \(n\) 归纳即可。

1.8.2 (b) 证明 \(\{a\}^*\subseteq L(A)\) 或 \(\{a\}^*\cap L(A)=\varnothing\)

对所有 \(n>0\)，

\[ \hat\delta(q_0,a^n)=q_0. \]

且 \(\varepsilon\) 也停在 \(q_0\)。

所以所有 \(a^n\) 的接受性完全由 \(q_0\in F\) 决定：

• 若 \(q_0\in F\)，则所有 \(a^n\) 都接受；
• 若 \(q_0\notin F\)，则一个也不接受。

---

1.9 习题 2.2.9：初态与唯一接受态的单步行为相同

设

\[ A=(Q,\Sigma,\delta,q_0,\{q_f\}) \]

且对所有 \(a\in\Sigma\)，

\[ \delta(q_0,a)=\delta(q_f,a). \]

1.9.1 (a) 对所有非空 \(w\)，证明

\[ \hat\delta(q_0,w)=\hat\delta(q_f,w). \]

写 \(w=ax\)。由习题 2.2.3：

\[ \hat\delta(q_0,ax) = \hat\delta(\delta(q_0,a),x), \]

\[ \hat\delta(q_f,ax) = \hat\delta(\delta(q_f,a),x). \]

而两者第一步状态相同，所以结果相同。

1.9.2 (b) 若非空串 \(x\in L(A)\)，证明 \(x^k\in L(A)\) 对所有 \(k>0\)

因为唯一接受状态是 \(q_f\)，

\[ \hat\delta(q_0,x)=q_f. \]

由 (a)，

\[ \hat\delta(q_f,x) = \hat\delta(q_0,x) =q_f. \]

因此每多读一份 \(x\)，仍回到 \(q_f\)。归纳得

\[ \hat\delta(q_0,x^k)=q_f, \]

故 \(x^k\in L(A)\)。

---

1.10 习题 2.2.10：两状态 DFA 的语言

教材给出的转移表为：

状态	0	1
\(\to A\)	\(A\)	\(B\)
\(*B\)	\(B\)	\(A\)

1.10.1 非形式化描述

\[ \boxed{L=\{w\in\{0,1\}^*\mid w\text{ 中 1 的个数为奇数}\}}. \]

理由：读 0 不改变状态；每读一个 1 就在 \(A,B\) 之间切换。初态 \(A\) 对应偶数个 1，接受态 \(B\) 对应奇数个 1。

1.10.2 归纳证明

建立更强不变量：对任意 \(w\)，

• 若 \(\#_1(w)\) 偶数，则最终在 \(A\)；
• 若 \(\#_1(w)\) 奇数，则最终在 \(B\)。

对 \(|w|\) 归纳。加 0 时奇偶不变且状态不变；加 1 时奇偶翻转且状态也翻转。因此不变量成立。

---

1.11 习题 2.2.11：三状态 DFA 的语言

教材转移表：

状态	0	1
\(\to *A\)	\(B\)	\(A\)
\(*B\)	\(C\)	\(A\)
\(C\)	\(C\)	\(C\)

1.11.1 语言

\[ \boxed{L=\{w\in\{0,1\}^*\mid w\text{ 不含子串 }00\}}. \]

1.11.2 更强的状态不变量

• \(A\)：尚未出现 00，且串为空或最后一个符号是 1；
• \(B\)：尚未出现 00，且最后一个符号是 0；
• \(C\)：已经出现 00。

对输入长度归纳即可验证三个状态含义始终正确。因为 \(A,B\) 都接受，而 \(C\) 拒绝，所以语言恰好是不含 00 的串。

2 2. NFA：教材习题 2.3.1–2.3.7

2.1 习题 2.3.1：NFA 转 DFA

教材 NFA：

状态	0	1
\(\to p\)	\(\{p,q\}\)	\(\{p\}\)
\(q\)	\(\{r\}\)	\(\{r\}\)
\(r\)	\(\{s\}\)	\(\varnothing\)
\(*s\)	\(\{s\}\)	\(\{s\}\)

从 \(\{p\}\) 做子集构造，得到可达集合：

DFA 状态	0	1	接受？
\(\{p\}\)	\(\{p,q\}\)	\(\{p\}\)	否
\(\{p,q\}\)	\(\{p,q,r\}\)	\(\{p,r\}\)	否
\(\{p,q,r\}\)	\(\{p,q,r,s\}\)	\(\{p,r\}\)	否
\(\{p,r\}\)	\(\{p,q,s\}\)	\(\{p\}\)	否
\(\{p,q,r,s\}\)	自身	\(\{p,r,s\}\)	是
\(\{p,q,s\}\)	\(\{p,q,r,s\}\)	\(\{p,r,s\}\)	是
\(\{p,r,s\}\)	\(\{p,q,s\}\)	\(\{p,s\}\)	是
\(\{p,s\}\)	\(\{p,q,s\}\)	自身	是

所有含 \(s\) 的集合状态接受。

---

2.2 习题 2.3.2：第二个 NFA 转 DFA

教材 NFA：

状态	0	1
\(\to p\)	\(\{q,s\}\)	\(\{q\}\)
\(*q\)	\(\{r\}\)	\(\{q,r\}\)
\(r\)	\(\{s\}\)	\(\{p\}\)
\(*s\)	\(\varnothing\)	\(\{p\}\)

可达子集表：

子集	0	1	接受？
\(\{p\}\)	\(\{q,s\}\)	\(\{q\}\)	否
\(\{q,s\}\)	\(\{r\}\)	\(\{p,q,r\}\)	是
\(\{q\}\)	\(\{r\}\)	\(\{q,r\}\)	是
\(\{r\}\)	\(\{s\}\)	\(\{p\}\)	否
\(\{p,q,r\}\)	\(\{q,r,s\}\)	自身	是
\(\{q,r\}\)	\(\{r,s\}\)	\(\{p,q,r\}\)	是
\(\{s\}\)	\(\varnothing\)	\(\{p\}\)	是
\(\{q,r,s\}\)	\(\{r,s\}\)	\(\{p,q,r\}\)	是
\(\{r,s\}\)	\(\{s\}\)	\(\{p\}\)	是
\(\varnothing\)	\(\varnothing\)	\(\varnothing\)	否

接受条件是子集包含 \(q\) 或 \(s\)。

---

2.3 习题 2.3.3：转换并描述语言

教材 NFA：

状态	0	1
\(\to p\)	\(\{p,q\}\)	\(\{p\}\)
\(q\)	\(\{r,s\}\)	\(\{t\}\)
\(r\)	\(\{p,r\}\)	\(\{t\}\)
\(*s\)	\(\varnothing\)	\(\varnothing\)
\(*t\)	\(\varnothing\)	\(\varnothing\)

可达 DFA 子集只有四个：

子集	0	1	接受？
\(\{p\}\)	\(\{p,q\}\)	\(\{p\}\)	否
\(\{p,q\}\)	\(\{p,q,r,s\}\)	\(\{p,t\}\)	否
\(\{p,q,r,s\}\)	自身	\(\{p,t\}\)	是
\(\{p,t\}\)	\(\{p,q\}\)	\(\{p\}\)	是

2.3.1 语言的非形式化描述

NFA 在某个 0 上可以从 \(p\) 进入 \(q\)。随后只要还有一个符号：

• 若下一符号是 0，可到接受态 \(s\)；
• 若下一符号是 1，可到接受态 \(t\)。

所以：

\[ \boxed{L=\{w\in\{0,1\}^*\mid w\text{ 中存在一个不是最后字符的 }0\}}. \]

等价地，串中含有子串 00 或 01。

---

2.4 习题 2.3.4：尽量利用非确定性设计 NFA

2.4.1 (a) 最后一个数字在前面已经出现过

字母表 \(\{0,1,\dots,9\}\)。

状态：

• 扫描态 \(s\)；
• 对每个数字 \(d\)，状态 \(q_d\) 表示“之前已经见过一个 d，现在等最后一个字符再次是 d”；
• 接受态 \(f\)，无出边。

在扫描态读数字 \(d\) 时：

\[ \delta(s,d)\supseteq\{s,q_d\}. \]

在 \(q_d\) 中：

• 对任意字符继续留在 \(q_d\)，以便等待更后的末位；
• 当读到 \(d\) 时额外分支到 \(f\)。

因为 \(f\) 无出边，只有当那个再次出现的 \(d\) 恰好是最后一个字符时，该路径才接受。

2.4.2 (b) 最后一个数字在前面没有出现过

NFA 可以“猜最终数字是什么”，但因为本节还没有 ε 转移，需要在读第一个字符时创建候选分支。

使用候选状态 \(q_d\)：表示“候选最终数字是 d，并且到目前为止还没有出现 d”。

读第一个数字 \(a\) 时：

• 允许直接进入接受态 \(f\)，处理长度 1 的串；
• 对所有 \(d\neq a\)，启动 \(q_d\)。

在 \(q_d\) 中：

• 读 \(c\neq d\)：留在 \(q_d\)；
• 读 \(d\)：只转到无出边接受态 \(f\)。

如果 d 在真正末尾之前出现，则该分支过早进入 \(f\) 并在后续输入上死亡；只有第一次出现 d 恰在末尾的分支能接受。

2.4.3 (c) 存在两个 0，使它们之间的字符个数是 4 的倍数

注意 0 也是 4 的倍数，因此 00 应接受。

NFA 扫描态 \(s\) 对 0/1 自环，并在某个 0 上猜它是“第一个 0”，同时进入 \(r_0\)。

\(r_i\) 记录自第一个 0 后已经经过的中间字符数模 4。

• \(r_0\) 上读 0 时可直接进入接受汇状态 \(f\)，因为中间字符数为 0；同时也可继续计数；
• 每读一个未作为第二个 0 的字符，\(r_i\to r_{i+1\bmod4}\)；
• 当处于 \(r_0\) 再读 0 时可进入 \(f\)；
• \(f\) 对 0/1 自环，因为一旦找到满足条件的一对 0，后续任意。

---

2.5 习题 2.3.5：补全定理 2.12 的归纳证明

要证明：若子集构造 DFA 的扩展转移满足

\[ \hat\delta_D(\{q_0\},w)=S, \]

那么该集合恰好等于 NFA 读完 \(w\) 后的所有可能状态：

\[ S=\hat\delta_N(q_0,w). \]

2.5.1 解答

对 \(|w|\) 归纳。

基础情况 \(w=\varepsilon\)：

\[ \hat\delta_D(\{q_0\},\varepsilon)=\{q_0\} = \hat\delta_N(q_0,\varepsilon). \]

归纳步令新串为 \(wa\)：

\[ \begin{aligned} \hat\delta_D(\{q_0\},wa) &=\delta_D(\hat\delta_D(\{q_0\},w),a)\\ &=\delta_D(\hat\delta_N(q_0,w),a)\\ &=\bigcup_{p\in\hat\delta_N(q_0,w)}\delta_N(p,a)\\ &=\hat\delta_N(q_0,wa). \end{aligned} \]

故成立。

---

2.6 习题 2.3.6：缺转移 NFA 与补死状态 DFA 的关系

若一个 NFA 在每个状态和输入符号上至多有一个后继，那么它其实就是“允许缺转移的 DFA”。

子集构造从单元素初态开始。因为每个单元素集合在每个字符上最多得到一个单元素集合，所以可达子集只能是：

• \(\{q\}\) 这样的单元素集合；
• \(\varnothing\)。

于是把 \(\{q\}\) 直接重命名为 \(q\)，并把 \(\varnothing\) 视为死状态，就得到：

• 原有定义的转移保持不变；
• 原来缺失的转移都进入死状态；
• 死状态对所有字符自环。

这正是“把部分 DFA 补成严格 DFA”的构造。

---

2.7 习题 2.3.7：例 2.13 中状态含义的证明

教材例 2.13 的 NFA 用状态 \(q_i\) 表示“从某个被猜中的 1 起，已经向后数了固定数量的位置”。要证明读完整个输入 \(w\) 后：

\[ q_i\text{ 可达} \iff w\text{ 的倒数第 }i\text{ 个符号是 }1. \]

2.7.1 证明思路

\(\Rightarrow\) 若最终可达 \(q_i\)，则这条路径必须在某个输入 1 上从扫描态启动，并随后每读一个符号向链上前进一步。最后停在 \(q_i\) 意味着从那个被猜中的 1 到输入末尾恰好有对应的距离，所以该 1 正是倒数第 \(i\) 个符号。

\(\Leftarrow\) 若倒数第 \(i\) 个符号确实是 1，则 NFA 在读到它时选择启动那条猜测分支。剩余符号数恰好使路径在输入结束时走到 \(q_i\)。因此 \(q_i\) 可达。

这个证明体现 NFA 设计的典型方法：

非确定地猜一个“关键位置”，然后用有限状态验证从该位置到结尾的有限距离关系。

3 3. 文本搜索：教材习题 2.4.1–2.4.2

3.1 习题 2.4.1：设计识别有限字符串集合的 NFA

3.1.1 (a) \(\{abc,abd,aacd\}\)，字母表 \(\{a,b,c,d\}\)

最自然的 NFA/前缀树：

start -a-> A
A -b-> AB -c/d-> F
A -a-> AA -c-> AAC -d-> F

\(F\) 为接受态，无出边。

3.1.2 (b) \(\{0101,101,011\}\)

start -0-> P0 -1-> P01
P01 -0-> P010 -1-> F
P010 -1-> F
start -1-> P1 -0-> P10 -1-> F

3.1.3 (c) \(\{ab,bc,ca\}\)，字母表 \(\{a,b,c\}\)

start -a-> A -b-> F
      -b-> B -c-> F
      -c-> C -a-> F

这三个例子都说明：有限语言总可以直接用有限前缀树识别，因此一定是正则语言。

---

3.2 习题 2.4.2：把 2.4.1 的 NFA 转为 DFA

因为上述 NFA 本身在每个状态/字符上至多有一个后继，所以只需补死状态 \(D\)。

3.2.1 (a) DFA

状态：

\[ S,A,AA,AB,AAC,F,D. \]

关键转移：

• \(S\xrightarrow a A\)；
• \(A\xrightarrow a AA\)，\(A\xrightarrow b AB\)；
• \(AA\xrightarrow c AAC\)；
• \(AAC\xrightarrow d F\)；
• \(AB\xrightarrow c F\)，\(AB\xrightarrow d F\)；
• 其他未列转移到 \(D\)；
• \(F\) 上任何额外字符到 \(D\)；
• \(D\) 自环。

3.2.2 (b) DFA

状态可取

\[ S,P0,P01,R,P1,F,D, \]

其中 \(R\) 合并原来的 010 和 10 前缀状态，因为二者未来都只需再读一个 1 即接受。

关键转移：

• \(S:0\to P0,1\to P1\)；
• \(P0:1\to P01\)；
• \(P01:0\to R,1\to F\)；
• \(P1:0\to R\)；
• \(R:1\to F\)；
• 其他到 \(D\)，\(F\) 后继续读也到 \(D\)。

3.2.3 (c) DFA

状态

\[ S,A,B,C,F,D. \]

• \(S:a\to A,b\to B,c\to C\)；
• \(A:b\to F\)；
• \(B:c\to F\)；
• \(C:a\to F\)；
• 其他到 \(D\)；
• \(F\) 继续读字符也到 \(D\)。

4 4. ε-NFA：教材习题 2.5.1–2.5.3

4.1 习题 2.5.1

教材 ε-NFA 转移表：

状态	ε	a	b	c
\(\to p\)	\(\varnothing\)	\(\{p\}\)	\(\{q\}\)	\(\{r\}\)
\(q\)	\(\{p\}\)	\(\{q\}\)	\(\{r\}\)	\(\varnothing\)
\(*r\)	\(\{q\}\)	\(\{r\}\)	\(\varnothing\)	\(\{p\}\)

4.1.1 (a) 各状态 ε-闭包

\[ \operatorname{ECLOSE}(p)=\{p\}, \]

\[ \operatorname{ECLOSE}(q)=\{q,p\}, \]

\[ \operatorname{ECLOSE}(r)=\{r,q,p\}. \]

4.1.2 (b) 接受的长度不超过 3 的串

按长度分类：

• 长度 0：无；
• 长度 1：c；
• 长度 2：ac, bb, bc, ca, cb, cc；
• 长度 3：

aac, abb, abc, aca, acb, acc,
bab, bac, bba, bbb, bbc, bca, bcb, bcc,
caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc

4.1.3 (c) 转换为 DFA

初始子集：

\[ \{p\}. \]

可达闭包子集只有三个：

\[ P=\{p\}, \quad Q=\{p,q\}, \quad R=\{p,q,r\}. \]

其中只有 \(R\) 接受。

DFA 状态	a	b	c	接受？
\(P\)	\(P\)	\(Q\)	\(R\)	否
\(Q\)	\(Q\)	\(R\)	\(R\)	否
\(R\)	\(R\)	\(R\)	\(R\)	是

---

4.2 习题 2.5.2

教材 ε-NFA：

状态	ε	a	b	c
\(\to p\)	\(\{q,r\}\)	\(\varnothing\)	\(\{q\}\)	\(\{r\}\)
\(q\)	\(\varnothing\)	\(\{p\}\)	\(\{r\}\)	\(\{p,q\}\)
\(*r\)	\(\varnothing\)	\(\varnothing\)	\(\varnothing\)	\(\varnothing\)

4.2.1 (a) ε-闭包

\[ \operatorname{ECLOSE}(p)=\{p,q,r\}, \]

\[ \operatorname{ECLOSE}(q)=\{q\}, \qquad \operatorname{ECLOSE}(r)=\{r\}. \]

所以空串已经被接受，因为初始闭包包含接受态 \(r\)。

4.2.2 (b) 长度不超过 3 的接受串

长度 0：

ε

长度 1：

a, b, c

长度 2：

aa, ab, ac, ba, bb, bc, ca, cb, cc

长度 3 中除了 bba, bbb, bbc 三个串之外，其余 24 个三字符串都接受。

4.2.3 (c) DFA

可达闭包集合：

\[ A=\{p,q,r\}, \quad B=\{q,r\}, \quad C=\{r\}, \quad D=\varnothing. \]

前三者接受，\(D\) 拒绝。

状态	a	b	c
\(A\)	\(A\)	\(B\)	\(A\)
\(B\)	\(A\)	\(C\)	\(A\)
\(C\)	\(D\)	\(D\)	\(D\)
\(D\)	\(D\)	\(D\)	\(D\)

---

4.3 习题 2.5.3：利用 ε 转移简化设计

4.3.1 (a) \(a^*b^*c^*\)

用三个带自环的阶段，并用 ε 边连接：

q0 --ε--> q1 --ε--> q2
 |         |         |
 a-loop    b-loop    c-loop

为了允许三个部分中任意一部分为空，可把 \(q_0,q_1,q_2\) 都设为接受态，或者再通过 ε 边连到一个统一接受态。

语言为

\[ \{a^i b^j c^k\mid i,j,k\ge0\}. \]

4.3.2 (b) 一次或多次重复 01，或者一次或多次重复 010

按题面自然解释：

\[ (01)^+\cup(010)^+. \]

从新初态 \(s\) 用两条 ε 边分别进入两个子自动机：

• 分支 1 识别 \((01)^+\)；
• 分支 2 识别 \((010)^+\)。

每个分支在完成一个块后既可以接受，也可以回到该块起点继续下一次重复。

Source note：中文题面“包含着 01 重复一次或多次或 010 重复一次或多次”存在轻微自然语言歧义。本解按最贴合本节 ε-NFA 模块拼接目的的读法 \((01)^+\cup(010)^+\) 处理，不把它改写成“任意位置包含这些子串”。

4.3.3 (c) 最后 10 个位置中至少有一个 1

NFA/ε-NFA 的好处是可以猜某个 1 是“最后 10 位中的那个 1”。

设置扫描态 \(s\) 对 0/1 自环。每当读到一个 1 时，额外通过 ε 进入计数链起点 \(r_0\)。

令

\[ r_0,r_1,\dots,r_9 \]

都为接受状态，并令

\[ r_i\xrightarrow{0,1}r_{i+1} \qquad (0\le i<9). \]

\(r_9\) 无普通出边。

如果输入结束时某条猜测路径处在 \(r_i\)，说明那个被猜中的 1 后面最多还有 9 个字符，因此它位于最后 10 个位置中。

5 5. 本章练习完成后的能力检查

若能不看答案完成下列任务，说明第 2 章已经基本掌握：

• 从语言描述直接设计 DFA 状态不变量；
• 对扩展转移函数做归纳证明；
• 完成任意 4–6 状态 NFA 的子集构造；
• 解释为什么 \(\varnothing\) 是 DFA 死状态；
• 对 ε-NFA 手算 ECLOSE；
• 把 ε-NFA 转成 DFA；
• 用非确定性表达“猜一个位置再验证”的模式。