在 DFA 最小化过程中，状态 p 和 q 对某个输入串 w 的反应不同：从 p 读取 w 后到达接受状态，而从 q 读取 w 后到达非接受状态。由此可知 p 和 q（）。
若存在输入串 w，使得从 p、q 出发读取 w 后，一个到达接受状态、另一个到达非接受状态，那么 w 能区分 p 和 q。两个状态对后续输入的接受行为不同，不属于同一等价类，因此不能在最小化 DFA 中合并。
选项分析
正确。w 是 p、q 的区分串，证明二者不等价。
错误。等价状态必须对所有后续输入串保持相同接受结果，本题已给出反例。
错误。状态名称不重要，但不能因此删除具有不同识别行为的状态。
错误。自动机图中的几何位置或连线相邻性不决定状态等价。
本题为什么容易错
有些同学只比较 p、q 的直接转移是否相同，忽略了转移后的状态还要继续比较。状态等价讨论的是任意长度后缀的最终接受行为，不只是下一步。
简短答案
DFA 最小化时，哪些状态不能合并，正确答案是 A（可区分，不能合并）。若存在输入串 w，使得从 p、q 出发读取 w 后，一个到达接受状态、另一个到达非接受状态，那么 w 能区分 p 和 q。两个状态对后续输入的接受行为不同，不属于同一等价类，因此不能在最小化 DFA 中合并。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 可区分，不能合并 | 本题正确答案 | 正确。w 是 p、q 的区分串，证明二者不等价。 | 看到题干核心场景时优先联想到它 |
| 等价，必须合并 | 本题干扰项 | 错误。等价状态必须对所有后续输入串保持相同接受结果，本题已给出反例。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 只有名字不同，可以直接删除 q | 本题干扰项 | 错误。状态名称不重要，但不能因此删除具有不同识别行为的状态。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 是否合并只取决于 p、q 当前是否相邻 | 本题干扰项 | 错误。自动机图中的几何位置或连线相邻性不决定状态等价。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 等价，必须合并：错误。等价状态必须对所有后续输入串保持相同接受结果，本题已给出反例。
- 只有名字不同，可以直接删除 q：错误。状态名称不重要，但不能因此删除具有不同识别行为的状态。
- 是否合并只取决于 p、q 当前是否相邻：错误。自动机图中的几何位置或连线相邻性不决定状态等价。
知识点详解
DFA 最小化通常先删除不可达状态，再按接受状态与非接受状态作初始划分。若同一分组中的两个状态在某个输入符号下转移到不同分组，就要继续拆分。迭代到分组稳定后，每个等价类可以合并为一个状态。等价状态的严格含义是：从两个状态出发，对任意输入串，最终要么都接受，要么都拒绝。存在一个让结果不同的输入串，就足以证明状态可区分。
备考速记
一个后缀能分出接受和拒绝，就证明两个状态不能合并。
DFA最小化 在可区分状态场景中的作用
DFA最小化在本题中的核心价值，是解决“在 DFA 最小化过程中，状态 p 和 q 对某个输入串 w 的反应不同：从 p 读取 w 后到达接受状态，而从 q 读取 w 后到达非接受状态。由此可知 p 和 q（）”这个场景问题。复习时不要只背选项名称，还要理解它为什么适用于该场景，以及它能解决哪类安全、流程或管理问题。
同类题怎么考
- 根据区分串判断两个状态是否等价。
- 使用分割法逐轮细化状态集合。
- 先删除不可达状态，再计算最小 DFA 的状态数。
DFA最小化 在软件设计师软考中的考法
软考选择题通常不会只考概念定义，还会把DFA最小化放到可区分状态场景中，要求判断它的作用、适用范围或与相近概念的区别。遇到这类题时，先抓住题干中的业务场景，再看哪个选项最能解决该场景下的核心问题。
解题思路
最小化不是看图画得近不近，而是做一场“后续考试”。给 p、q 同样的后缀 w，一个最终通过、一个最终不通过，说明它们承担的语言识别功能不同。只要找到这一份能分出结果的试卷，就没有资格把两个状态合并。
考点定位
DFA 状态等价要求对任意后续输入串都具有相同接受行为；只要能找到一个区分串，就必须把两个状态分到不同等价类。
易错提醒
- 认为两个非接受状态天然等价。
- 只比较一个输入字符的去向，不继续检查目标状态所属分组。
- 没有先删除从初始状态不可达的状态，就直接统计最小状态数。
备考提示
- 划分法先把接受状态和非接受状态分开，再根据各输入符号的目标分组反复细分。
- 找到区分串后立即记录，它既能证明不能合并，也能帮助检查划分结果。
你可能还想了解
- DFA 等价状态的定义是什么？
- 为什么接受状态和非接受状态必须先分组？
- 怎样用划分法完成 DFA 最小化？
- 不可达状态为什么要在最小化前删除？
本文小结
输入串 w 能让 p、q 的最终接受结果不同，因此 w 是区分串，p、q 不等价，不能合并。状态最小化比较的是所有后续输入的识别行为，不是图中的位置。