Homework 2 · 完整解析与过程

CSCI3130 · 2026–2027 第一学期

题目：HW02 原件（本地课件）（2026 年 9 月 28 日至 10 月 5 日）。配套：英文参考答案（本地资料）。本文为独立整理的学习用解析，非官方答案。

先分清三种“状态”

本次作业的关键，是分清 DFA 的单个状态、NFA 的一条运行路径，以及 NFA 读完一个前缀后所有可能状态组成的集合。

**DFA：**每个状态对 a、b 都恰有一个下一状态。读完输入后，只有当前位置决定是否接受。

**NFA：**一个状态对同一符号可以有多个下一状态，也可以没有。只要存在一条路径恰好读完整个输入，并停在接受状态，就接受。其他路径失败不影响这一结果。

**带 λ 的 NFA：**λ 转移不消耗输入。计算当前可能状态时，要把不读字符也能到达的状态一起算进去。λ-闭包包括出发状态本身，并包括经零次或多次 λ 转移可达的状态。

符号约定：→ 标初态，* 标接受态；∅ 是空集合；空串记为 λ。空集合不是空串：∅ 作为下一状态集合表示这条分支无法继续。

Q1：奇数个 a，并且以 b 结尾（30 分）

完整任务：在字母表 {a,b} 上构造 DFA，恰好接受 a 的个数为奇数且以 b 结尾的所有串，并简要解释每个状态的含义。

1. 把接受条件拆开

题目要求同时满足：a 的数量为奇数；最后一个字符是 b。例如 ab、abb、aaab 应接受；空串、b、a、aab 应拒绝。不能只检查其中一个条件。

我们不必记住 a 的精确数量，只需记住奇偶性。读取 a 会翻转奇偶性，读取 b 不会改变奇偶性。还要知道当前最后一位是否是 b。

2. 按四种情况设置 q0、q1、q2、q3

本版按你的要求使用四个状态，并以 q0 为初态。状态必须有明确的含义，才能决定后续转移；q0 除了是初态，还表示“偶数个 a，且当前不是以 b 结尾”。空串属于这一情况，读到 aa 后也会回到 q0。

Q1 四状态 DFA（本地素材，未公开）

图中双圆圈 q3 是唯一接受态。两条斜线相交处没有状态点，只是画线交叉，不能在那里换轨。

3. 逐项推出八条转移

从 q0 读 a：偶数变奇数，末尾是 a，去 q1。读 b：仍是偶数个 a，末尾变为 b，去 q2。

从 q1 读 a：奇数变偶数，末尾为 a，回 q0。读 b：仍是奇数个 a，末尾变为 b，去 q3。

从 q2 读 a：偶数变奇数，末尾为 a，去 q1。读 b：仍是偶数个 a 且末尾为 b，留在 q2。

从 q3 读 a：奇数变偶数，末尾为 a，回 q0。读 b：仍是奇数个 a 且末尾为 b，留在 q3。

形式化定义：M₁ = ({q0,q1,q2,q3}, {a,b}, δ, q0, {q3})。每个状态对 a、b 都恰好有一个下一状态，因此是完整 DFA。

4. 验证与正确性证明

ab：q0 →[a] q1 →[b] q3，接受。aab：q0 →[a] q1 →[a] q0 →[b] q2，拒绝。aaab：q0 →[a] q1 →[a] q0 →[a] q1 →[b] q3，接受。b：q0 →[b] q2，拒绝。空串停在 q0，拒绝。

严格证明使用状态不变式：空串满足 q0 的含义；假设任意前缀的状态含义成立，上述八条转移保证再读 a 或 b 后仍成立。由归纳法，状态含义对所有输入成立。唯一接受态 q3 恰好表示“奇数个 a 且以 b 结尾”，故没有漏收或误收。

q0 作为初态不意味着禁止返回。aa 会返回 q0，此时仍符合它的含义。四状态方案合法；虽然 q0 与 q2 可以合并以得到三状态 DFA，但本题不要求最少状态，本版保留你指定的四个状态。

为什么四种含义不等于四个不可合并的状态（补充）：q0 与 q2 都是“偶数个 a”的非终态，且各自读 a 都去 q1、读 b 都去 q2，因此从它们出发对任何未来后缀的行为相同。区别只在已经读过的末尾是不是 b，而当当前 a 数为偶数时，这个旧末尾信息不再影响未来是否接受。q1 与 q3 却不能合并：不再读任何输入时，一个拒绝、一个接受。因此这张四状态表适合逐条件构造，但不能把它当作四状态最小性的证明。

Q2：恰好四个状态，识别以 aa 或 bb 结尾的串（30 分）

完整任务：在字母表 {a,b} 上构造恰好四个状态的 NFA，恰好接受以 aa 或 bb 结尾的串。

1. 将目标写成“任意前缀 + 指定后缀”

目标语言可写成 {a, b}*{aa, bb}。前面可以是任意字符串，包括空串；最后两位必须相同。aa、bb、baa、abb 应接受；空串、a、b、ab、ba、aab 应拒绝。

“含有 aa 或 bb”与“以 aa 或 bb 结尾”不一样。例如 aab 中含有 aa，但末尾是 ab，所以必须拒绝。

2. 用非确定性猜测最后两位从哪里开始

建立初态 s，并让它对 a、b 都有自环，负责读取任意前缀。读到 a 时，还允许分出一条到 u 的路径，猜测这个 a 是倒数第二位；读到 b 时，允许分出一条到 v 的路径，猜测这个 b 是倒数第二位。

u 只允许再读一个 a，进入接受态 t；v 只允许再读一个 b，进入同一个 t。两种后缀共用接受态，于是状态恰好为 s、u、v、t 四个。

Q2 四状态 NFA（本地素材，未公开）

形式化定义：M₂ = ({s, u, v, t}, {a, b}, δ, s, {t})。不需要 λ 转移。NFA 允许空转移集合，因此不需要另加死状态；另加死状态反而会超过四状态限制。

若手画状态图：给 s 画 a,b 自环；画 s →[a] u →[a] t 和 s →[b] v →[b] t；t 画双圆圈，不画任何出边。

3. 为什么 t 不能有自环？

进入 t 只说明某一条路径刚刚读到了 aa 或 bb。要确保这两个字符在末尾，必须使这条路径无法继续读取更多字符。如果 t 有 a、b 自环，那么 aab 会在读完 aa 后进入 t，再读 b 仍留在 t，造成误收。

t 没有出边不会妨碍较长的合法输入，因为留在 s 的其他分支仍可稍后重新猜测后缀起点。

4. 用可能状态集合追踪实例

对 abb：

{ s } →[a] {s, u} →[b] {s, v} →[b] {s, v, t}。

最终集合含 t，故接受。对应的一条接受路径是 s →[a] s →[b] v →[b] t。

对 aab：

{ s } →[a] {s, u} →[a] {s, u, t} →[b] {s, v}。

读完前两个 a 时虽然存在位于 t 的路径，但输入尚未结束；这条路径无法再读 b。最终集合不含 t，所以拒绝。这正好实现“结尾”的要求。

从集合的生命周期看一次错误猜测（补充）：在 aab 的第三步，旧集合 {s,u,t} 中每个状态都只读取这一次 b：s 贡献 {s,v}，u 与 t 各贡献空集，新的集合因此为 {s,v}。不能因为新集合刚加入 v，又让 v 在同一步读取同一个 b 到 t；那相当于把一位输入用了两次，会误收 aab。实现或手算时，必须区分本步的旧集合与新集合，先收集完结果再换步。

5. 证明识别的语言恰好正确

不会误收：任何接受路径都必须在读完整个串时到达 t。进入 t 的前一状态只能是 u 或 v，而进入 u、v 的前一状态只能是 s。因此该路径最后两步必为 aa 或 bb，整个串也必以其中之一结尾。

不会漏收：若输入为 xaa，就让 s 的自环读完 x，再走 s →[a] u →[a] t；若输入为 xbb，则走 s →[b] v →[b] t。每个目标串都存在接受路径。

Q3(a)：按子集构造逐格核验（25 分）

原题的待检查 DFA M（保留错误，尚未修正）：初态 A，题面只将 E 标为接受态。各标签固定代表下表子集。

Q3(a) 完整要求：用子集构造检查每个已列状态，包括在这张原表中不可达的状态；保留这些子集标签，给出修正表，并对每个改动写出集合计算和 λ 移动。Q3(b)：确定修正机的接受态及原因；给出 NFA N 与这张原始 M 不一致的最短串，分别跟踪，并证明不存在更短区分串。下面先完整列 N，再执行修正。

1. 抄清 NFA，先处理 λ-闭包

Q3 原始 NFA（本地素材，未公开）

唯一的 λ 边是 q₂ → q₀。用 Cl(S) 表示集合 S 的 λ-闭包：若 S 含 q₂，就补上 q₀；否则保持 S 不变。因为 q₀ 没有 λ 出边，这里无需继续添加其他状态。

例如 Cl({q₂}) = {q₀, q₂}，Cl({q₂, q₃}) = {q₀, q₂, q₃}，Cl({q₁, q₃}) = {q₁, q₃}，Cl(∅) = ∅。

2. 子集状态的含义与计算公式

DFA 的一个状态表示：NFA 读完同一输入前缀并允许所有 λ 移动后，可能处于哪些状态。这是“可能性集合”，不是从中任意挑一个状态。

本题 A 到 T 的标签已经指定，不能改成自己喜欢的集合。逐个检查可知，所有给定集合本身都已 λ-闭合，特别是含 q₂ 的 C、F 都包含 q₀。

因此每读一个字符 x，就用以下公式：

δ_D(S, x) = Cl( ⋃ [δ_N(q, x) : q ∈ S] )。

也就是：先对 S 中每个状态分别读取 x，再把结果取并集，最后补做所有 λ 移动。若起始集合未闭合，通用做法还要先对它求闭包；本题各标签已满足这个条件。

初态为 Cl({q₀}) = {q₀} = A。下面检查全部七行、十四个输入转移，不因 F 在原表中不可达就跳过它。

3. A、B、C 三行

A = {q₀}：

• 读 a：Cl(δ_N(q₀,a)) = Cl({q₁}) = {q₁} = B，原表正确。
• 读 b：Cl(δ_N(q₀,b)) = Cl(∅) = ∅ = T，原表正确。

B = {q₁}：

• 读 a：Cl(δ_N(q₁,a)) = Cl(∅) = ∅ = T，原表正确。
• 读 b：Cl(δ_N(q₁,b)) = Cl({q₂}) = {q₀,q₂} = C，原表正确。这里从 q₂ 走 λ 边补入 q₀，不额外消耗输入。

C = {q₀,q₂}：

• 读 a：Cl({q₁} ∪ {q₃}) = {q₁,q₃} = D，原表正确。
• 读 b：Cl(∅ ∪ ∅) = ∅ = T，原表正确。

读完 ab 到 C，含义是 NFA 既可能停在 q₂，也可能从 q₂ 通过 λ 到 q₀。再读 a 时，两条可能分别到 q₃ 和 q₁，所以必须保留二者。

4. D、E、F、T 四行

D = {q₁,q₃}：

• 读 a：Cl(∅ ∪ {q₃}) = {q₃} = E，原表正确。
• 读 b：Cl({q₂} ∪ {q₃}) = Cl({q₂,q₃}) = {q₀,q₂,q₃} = F。原表写成 C，必须改为 F。

**第一处错误的原因：**q₁ 读 b 到 q₂，再由 λ 边补入 q₀；同时 q₃ 读 b 仍在 q₃。原表的 C = {q₀,q₂} 丢掉了 q₃ 这条仍然存活的路径。

E = {q₃}：

• 读 a：Cl({q₃}) = {q₃} = E，原表正确。
• 读 b：Cl({q₃}) = {q₃} = E，原表正确。

F = {q₀,q₂,q₃}：

• 读 a：Cl({q₁} ∪ {q₃} ∪ {q₃}) = Cl({q₁,q₃}) = {q₁,q₃} = D。原表写成 E，必须改为 D。
• 读 b：Cl(∅ ∪ ∅ ∪ {q₃}) = {q₃} = E，原表正确。

**第二处错误的原因：**q₀ 读 a 到 q₁，q₂ 和 q₃ 读 a 都到 q₃。集合的重复元素只保留一次，但 q₁ 不能删除。结果不含 q₂，而且 q₁、q₃ 没有 λ 出边，闭包不再添加状态。

T = ∅：

• 读 a：Cl(∅) = ∅ = T，原表正确。
• 读 b：Cl(∅) = ∅ = T，原表正确。

空集合表示没有任何仍可运行的 NFA 分支。从没有分支的情况继续读符号，也不会凭空出现新分支。因此 T 是 DFA 的死状态。

5. 最终修正表与可达性

先对照题目原始 DFA：只有 E 是双圆圈，F 不可达；红色边中包含与指定子集不符的转移。F 到 E 的合并标签中，只有 a 错误，b 正确。

Q3 原始错误 DFA（本地素材，未公开）

修正后 D、E、F 都是双圆圈；D 读 b 到 F，F 读 a 到 D。

Q3 修正 DFA（本地素材，未公开）

**转移只修改两格：D 的 b 列由 C 改为 F；F 的 a 列由 E 改为 D。**接受标记还需增加 D 和 F，原因见下一节。

原表中，从 A 可达的状态之间没有一条边进入 F，因此 F 原先不可达。但题目明确要求检查每个列出的集合。改正 D 的 b 转移后，abab 的路径为 A → B → C → D → F，F 已成为可达状态，其错误转移也会实际影响后续运行。

修正后七个状态都有到达见证：A 对应空串，B 对应 a，C 对应 ab，D 对应 aba，E 对应 abaa，F 对应 abab，T 对应 b。无须新增状态，也不能把标签不同但语言行为相同的集合直接合并，因为本题要求保留给定标签。

Q3(b)：接受状态、最短反例与最短性证明（15 分）

1. 为什么 D 和 F 也接受？

NFA 的接受语义是“存在一条接受路径”。所以子集状态只要包含任意一个 NFA 接受态，就必须是 DFA 接受态；不要求集合里所有状态都接受，也不要求集合等于单元素集合 {q₃}。

本题 NFA 唯一接受态为 q₃：D = {q₁,q₃}、E = {q₃}、F = {q₀,q₂,q₃} 都含 q₃。因此修正后的接受状态集合是 {D,E,F}。

D 中还含 q₁，不会抵消 q₃ 的接受路径；F 中还含 q₀、q₂，道理相同。A、B、C、T 不含 q₃，所以不接受。

2. 最短区分串是 aba

这里比较的是 NFA N 与题目给出的原始 M。原始 M 的唯一接受态是 E，必须沿用这一点，不能先修正接受集合再找反例。

对 N：最后集合中含 q₃，因此接受。具体接受路径为 q₀ →[a] q₁ →[b] q₂ →[a] q₃。这条路径不需要使用 λ 边；λ 移动是可选的，NFA 不必一到 q₂ 就离开它。

对原始 M：A →[a] B →[b] C →[a] D。D 在原始机器里不是接受态，而输入已读完，故拒绝。

因此 aba 被 N 接受、被原始 M 拒绝，长度为 3。

3. 为什么长度 0、1、2 都不可能区分？

结构性证明：N 必须先从 q₀ 读 a 到 q₁，再读 b 到 q₂，最后读 a 到 q₃。第一次到达 q₃ 至少消耗三个字符。q₂ →[λ] q₀ 只会返回起点，不能让 q₃ 更早到达。N 因而拒绝全部长度小于 3 的串。

原始 M 的唯一接受态 E，要首次到达它，最少需沿 A → B → C → D → E 走四步，例如输入 abaa。F 原先不可达，不能通过它的出边缩短路径。因此 M 也拒绝全部长度小于 3 的串。

也可以穷举这七个更短的串作交叉检查：

所以不仅找到了一个反例，也证明了没有更短反例。注意 aba 尚未走到两处错误的转移格；仅凭原表漏标 D 为接受态，就已足以造成分歧。

用乘积搜索解释“最短”而不靠猜（补充）

比较 N 与原始 M 时，可把搜索节点记成 $(S,q)$，其中 S 是 N 的 λ-闭合状态集合，q 是原始 M 的单个状态。初始节点为 ({q0},A)，读同一个字符后两侧同时更新；若“q3∈S”与“q=E”真假不同，就找到了区分串。按长度逐层搜索即 BFS，第一次发现分歧时，之前所有更短的可达节点都已检查，所以得到的是最短反例。记录每个节点的前驱和字符，就能回溯完整见证，而不是只报告长度。

本题沿 a、b、a 到达 ({q1,q3},D)，满足分歧条件。注意第二侧始终用原始 M：若搜索前把 D 先改成终态，验证对象就变了，aba 将不再是反例。若节点重复可以不再展开，因为同一对状态面对任意后缀的未来行为相同；有限状态乘积使搜索最终能够结束。这也连接了作业的“最短反例”与正则语言等价判定算法。

4. 用语言形状再次检查答案

在首次进入 q₃ 之前，从 q₀ 回到 q₀ 的循环只能是 q₀ →[a] q₁ →[b] q₂ →[λ] q₀，每圈消耗 ab。然后再读 aba 到达 q₃。进入 q₃ 后，a、b 都可以继续自环。

所以 N 的语言是 $(ab)^\ast aba\{a,b\}^\ast$，等价地是 $(ab)^+a\{a,b\}^\ast$。它的最短串确实是 aba。修正后的 D、E、F 都含 q₃；一旦进入这三个状态之一，后续转移仍留在这三个接受态之中，也符合“进入 q₃ 后任何后缀都可接受”的性质。

这一语言表达式用于额外交叉检查，不替代题目要求的十四格核验、修改格集合计算和最短性论证。

来源与证据

2026-10-13 重新核对 HW02-2026T1 题面 p.1 的文字、NFA 和待修正 DFA。本文保留全部题干约束，题图均有完整文字转移表，图片不加载也能学习；解法为补充解析。