CSCI3130 T02 · Part 4 分块语言 NFA

课程：CSCI3130 · 2025T1 本讲：第4部分 / 共4部分 · T02-2025T1.pdf（本地课件） p.12–15 定位：用一个可空的返回边接受任意多个ab或abc块。 前后：上一份 奇偶状态 · 下一单元 T05 Part 1 承接：#L01-47 星闭包、#L02-10 NFA、#L02-11 λ转移

零个块也必须接受（p.12–13）【已会】

p.12为导航，p.13出题。

题面块（T02 · Problem 4 · PDF p.13；公式按讲义重排）：

p.13 Construct an nfa with three states that accepts the language $\{ab,abc\}^{\star}$

每个块都先读a、再读b，然后可以有c。星闭包允许零块，所以初态必须接受，或能沿λ走到终态。不能把输入理解为“只接受ab或abc一次”。

四状态图到三状态图（p.14–15）

图（p.14）：初态q0，终态q0、q2、q3；q0→q1标a、q1→q2标b、q2→q3标c、q2→q1标a、q3→q1标a，其余无边。看什么：结束一个ab或abc块后都可开启下一块。

图（p.15下图）：初态且唯一终态q0，q0→q1标a，q1→q2标b，q2→q0标c或λ。看什么：λ返回完成ab块，读c返回完成abc块，恰省去单独的块结束状态。每次回q0读过的非空串只能是ab或abc；任意这些块的拼接都可逐块沿图执行，双向正确性成立。

算一遍：ababc按q0— a →q1— b →q2— λ →q0— a →q1— b →q2— c →q0，读完接受。aba读完只能到q1，拒绝；abcab最后在q2可沿λ回q0，因此接受。不要因为最后一个输入符号读完时暂在q2就漏掉λ闭包。

原三态机的全部转移集合：δ(q0,a)={q1}，δ(q1,b)={q2}，δ(q2,c)={q0}，δ(q2,λ)={q0}；其余均为空集。字母表{a,b,c}，初态q0，终态集{q0}。未画的边表示没有分支，不是保持当前状态。

同时保留“块已完成”和“还可接 c”的解释（补充）

三状态 NFA 读完 ab 后的状态集合是 $\{q_2,q_0\}$：q2 表示刚走完 a、b，q0 来自 q2 的 λ 转移，表示也可以把 ab 当成完整块。这两个解释必须同时保留。若下一个字符是 a，只能从 q0 开始新块；若是 c，则从 q2 完成 abc。选择 λ 转移不是把 q2 永久删掉，也不是自动贪心地选较短块。

用 ε-闭包逐步算自取输入 abc：初始集合为 {q0}，读 a 后为 {q1}，读 b 后为 {q2,q0}，读 c 后为 {q0}，故接受。对 abcc，再读一个 c 没有任何可走分支，集合变成空集而拒绝。这直接区分了“c 可以结束 abc 块”和“c 可以任意出现”：星号重复的是整个 ab 或 abc 块，并未授予每个字符独立重复的权限。

本讲核心考点

• 星闭包包含空串（p.13–15，C 级）。
• λ返回与c返回分别完成ab、abc块（p.15，C 级）。
• 读完后仍要考虑λ可达终态（p.15，C 级）。

附录

原图全部边、接受条件和样例路径已在正文展开。

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 HW01-2025T1-题目.pdf、HW01-2026T1-题目.pdf、HW02-2025T1-题目-更新.pdf、HW03-2025T1-题目.pdf、HW04-2025T1-题目.pdf、HW05-2025T1-题目.pdf、期中练习-含解答-学期待核.pdf、期末-2022T1-资料包.pdf、Final-Exam-2023T1-题目.pdf、Final-Exam-2024T1-题目.pdf、Final-Exam-2025T1-题目.pdf、期末-2023T1-资料包.pdf、期末-2024未核-资料包.pdf；未识别用途的 PDF：无

• 原件：T02-2025T1.pdf（本地课件），PDF p.12–15；两图已目视。

• 本次独立学习修订：核对对应辅导原件全部文本与本篇题面，保留完整规则、转移与证明。视觉复核物理页5、11、14–15。