Vince Jiang

CSCI3130 / 课程伴读 · 本站更新

CSCI3130 L02 Part 4/4 Reduction of the Number of States in FA

课程：CSCI3130 Formal Languages and Automata Theory · 2026T1（沿用既有原件版本标记） 本讲：L02 Part 4/4 Reduction of the Number of States in FA · 原件 lec2.pdf（本地课件） p.202–207 定位：分清不可达状态与等价状态，用区分后缀将状态分组，算出原例最小化后的转移表。 前后：上一份 L02-P3-DFA与NFA等价.md · 下一份 L03-P1-正则表达式.md

p.202 Outline 分节页；此部分在Outline中带星号，伴读保留原内容，不据星号推断考试范围。

Reduction of the Number of States in FA

先去掉永远到不了的状态（p.203）【新】

图（p.203）：Example 2.14。 元素：初态q0，终态q3、q4；q0读0到q1、读1到q2；q1读0到q2、读1到q3；q2读0自环、读1到q4；q3、q4在0、1上自环；q5读0自环、读1到q4，却没有任何从初态可达部分进入q5的边。 看什么：q5不可达，因此无论是否保留它，任何真实输入从q0开始的运行都不会使用它。

从q0做可达性扩展：第一轮加入q1、q2，第二轮加入q3、q4，之后不再新增，q5始终不出现。删不可达状态与“没有路径到终态”不同：可达的拒绝陷阱也可能是完整DFA所必需的。这里删q5无需改变其余运行。

表（p.203）：删去不可达 q5 后的全部可达转移。

状态 读0 读1 是否终态
q0 q1 q2 否
q1 q2 q3 否
q2 q2 q4 否
q3 q3 q3 是
q4 q4 q4 是

q0、q1、q2、q3、q4 的可达输入见证分别是 λ、0、1、01、11。不可达的 q5 虽然可以走1到终态 q4，但它不能被任何从初态出发的输入使用；因此“能到终态”和“能从初态到达”是方向不同的两项检查。

等价的标准是所有后缀（p.204）【新】

p.204 For all w∈Σ∗w\in\Sigma^{\ast}

公式按讲义重排。两个状态p、q不可区分，指从它们分别开始读同一个任意后缀w，最终接受性总是相同：

δ∗(p,w)∈F  ⟺  δ∗(q,w)∈F. \delta^{\ast}(p,w)\in F\iff\delta^{\ast}(q,w)\in F.

要证明可区分只需找到一个后缀使一边接受、另一边拒绝。空串也是后缀，所以一终态与一非终态立即被空串区分；两个当前都非终态，仍可能被长度1或更长后缀区分。

补充：原页有拼写“Two steps”，这里按上下文讲两个states；不把排版拼写当成新的数学概念。

先按接受性分组（p.205）

图（p.205）：Example 2.15。 元素：初态q0；终态q2、q4；非终态q0、q1、q3。边为q0读0到q1、读1到q3；q1读0到q2、读1到q4；q2读0到q1、读1到q4；q3读0到q2、读1到q4；q4在0、1上自环。 看什么：先分非终块 {q0,q1,q3}\{q_0,q_1,q_3\} 与终块 {q2,q4}\{q_2,q_4\}，再检查各字符的去向是否落在相同块。

q0与q1都非终，但后缀0能区分：q0读0到非终q1，q1读0到终态q2，因此必须拆开。q1与q3在0上都到q2、在1上都到q4，所以两者下一步甚至完全相同，今后对任意后缀也无法区分，可保留在一块。

稳定划分与最终机器（p.206–207）

p.206 再检查两个终态：q2读0到非终q1，而q4读0仍在终态q4，所以用后缀0拆开。最终四块为A={q0}、B={q1,q3}、C={q2}、D={q4}；初态A，终态C、D。

合并后的状态 0 1
A B B
B C D
C B D
D D D

检查为何稳定：B内两个原状态在每个输入上到同一个目标块；其余块都只有一个状态。A与B由0区分，C与D由0区分，任一非终块与终块由空串区分，所以四块不能继续合并。算一遍：输入00从A→B→C接受；000从A→B→C→B拒绝；01从A→B→D接受，与原机逐步运行一致。p.207 为Questions结束页。

逐轮分块记录（由 p.205–206 展开）：初分 P0={{q0,q1,q3},{q2,q4}}P_0=\{\{q_0,q_1,q_3\},\{q_2,q_4\}\}。对每个状态记录读0、读1分别到哪个旧块，q0 的签名是“非终、非终”，q1、q3 为“终、终”，q2 为“非终、终”，q4 为“终、终”。签名只在同一个旧块内部比较，不能把 q4 与 q1、q3 合并，因为空串已能区分终态与非终态。

因此下一轮分成 {q0}、{q1,q3}、{q2}、{q4}。再按这四块检查：q1、q3 仍都读0到 {q2}、读1到 {q4}，无需进一步拆分。四块的可达见证可取 λ、0、00、01；结合上面的区分后缀，才得到这台四状态机确实最小。

考试角度：（C 级 通识）这类知识点常见考法是给两个状态找最短区分后缀，或逐轮写划分而非直接凭图形相似合并。

考试角度：（A 级：期末-2022T1-资料包.pdf Q1，对应以ba结尾的最小DFA；扫描卷题面经视觉读取，练习卷不冒称正式考卷。）见附录 A1。

从分块失败反推出区分后缀（补充）

第一轮按终/非终划分，是因为空串已经能区分这两类。下一轮如果 p、q 在字符 a 上分别进入两个已经区分的块，则 a 也不能让 p、q 合并。更一般地，假设后继由后缀 v 区分，那么从原状态读 av，先走 a 到那对后继，再走 v，就得到 p、q 的区分后缀。区分证据是从后继一步步往前接字符产生的，不是看图形长得不同。

稳定之后为什么可以任选块内一个状态来画合并后的出边？因为同块任意 p、q 在每个字符下都去同一个目标块；若选不同代表会得到不同目标，说明划分还未稳定。归纳到任意后缀，同块状态最终始终落在同类接受块，故合并不会改变语言。另一方面，为不同最终块给出区分后缀，再结合各块从初态可达，才证明没有更小的等价 DFA；单纯“我再也看不出可合并者”不是最小性证明。

自检：所有无路到终态的可达状态可否直接删除？

完整 DFA 要求每个状态与字符组合都有后继。

展开推理与答案

这些状态的未来接受语言都为空，可以合并成一个拒绝陷阱；若有输入会到它，直接删掉会破坏完整转移定义。真正可以无影响删除的是从初态不可达的状态。

本讲核心考点

  • 不可达状态与可达拒绝陷阱不同（p.203；C 级）。
  • 等价需对所有后缀一致，可区分只需一个反例后缀（p.204；C 级）。
  • 原例最小化为四个状态块（p.205–206；C 级）。

附录

本部分没有需要另列的推导；定义与算例在相应页段内。

A1 作业/往年题演练（非讲义内容）：以ba结尾的最小DFA

题面块（期末-2022T1-资料包.pdf（本地课件） · Q1 · p.2，扫描件视觉读取；公式重排）：

p.2 Give a minimal DFA for the language L={w∈{a,b}⋆:w ends with the substring ba}L=\{w\in\{a,b\}^{\star}:w\text{ ends with the substring ba}\}.

p.2 Prove that your DFA is minimal by giving, for every pair of distinct states, a string to distinguish the pair.

三态q0（没有匹配后缀）、q1（末尾b）、q2（末尾ba）。q0初态、q2唯一终态。完整转移：q0读a→q0、b→q1；q1读a→q2、b→q1；q2读a→q0、b→q1。例如bba路径q0→q1→q1→q2接受，baa末尾再a回q0拒绝。

可达性：λ、b、ba分别到三态。q2与q0、q1均用空后缀λ区分，因为q2本身终态而另两态不是；q0与q1用后缀a区分，前者到q0拒绝，后者到q2接受。每对可达状态都可区分，因此不能合并，三态最小。

回到正文：以ba结尾的最小DFA

来源与证据

历史版本考试证据（本次未重新读取全部试卷）：读了 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：无

  • 原件：lec2.pdf（本地课件），PDF p.202–207。

  • 本次复核：2026-10-13；逐页读取 lec2.pdf 文字，核对主要机器图与图片题例，补全转移表及主线证明。p.53 原图在 PDF 渲染中缺失部分图元，正文已提供明确标为补充的完整构造。