NFA确定化与DFA最小化

$\epsilon$- 闭包与 $Ia$ 计算

$\epsilon$- 闭包：从状态 $s$ 出发，仅通过 $\epsilon$ 边可达的所有状态集合。

$Ia$ 计算：从状态集 $T$ 出发，经输入 $a$（允许中间 $\epsilon$ 转移）到达的状态集：

$$Ia=\epsilon \text{-closure}(\{q^{\prime }\mid \exists q\in T,(q,a)\to q^{\prime }\})$$

$\epsilon$- 闭包三步计算法

1. 初始：$closure=\{s\}$
2. 若 $p\in closure$ 且 $p\stackrel{\epsilon }{\to }q$，则将 $q$ 加入 $closure$
3. 重复直到 $closure$ 不再增大

重点 $\epsilon$- 闭包和 $Ia$ 计算是子集构造法的基础。

子集构造法（NFA → DFA）

定理：$\forall$ NFA $\exists$ 等价 DFA（二者识别的语言相同）。

算法步骤：

1. 从 NFA 初态 $S_0$ 出发，计算 $\epsilon \text{-closure}(\{S_0\})$，作为 DFA 的初态 $I_0$
2. 对每个新产生的 DFA 状态 $I$，对每个 $a\in \Sigma$ 计算 $Ia=\epsilon \text{-closure}(move(I,a))$
3. 若 $Ia$ 尚未存在，则加入 DFA 状态集
4. 重复直至无新状态产生
5. 含有 NFA 终态的 DFA 状态标记为终态
6. 重命名 DFA 状态

示例：NFA 有状态 $\{0,1,2\}$，$\epsilon$- 闭包计算后得到 DFA 状态 $A=\{0,1,2\}$, $B=\{1,2\}$, $C=\{2\}$ 等。

重点 子集构造法是 NFA 确定化的标准算法，常嵌入综合大题。

DFA 最小化（两步法）

第一步：删除不可达状态

从初态出发做 DFS/BFS，标记所有可达状态，删除不可达状态及其出边。

重点 不可达状态检测（DFS 遍历）。

第二步：划分法合并等价状态

等价状态：$\forall \omega \in {\Sigma }^{\ast }$，从 $s_i$ 和 $s_j$ 出发读入 $\omega$ 后，要么都接受、要么都拒绝。

划分法步骤：

1. 初始划分：$\Pi =\{Z,S\setminus Z\}$（终态集 vs 非终态集）
2. 细化：对每个组 $G$，若 $G$ 中状态对某个 $a\in \Sigma$ 转移到不同组，则分裂 $G$
3. 重复直到所有组不再分裂
4. 每个组内状态等价，合并为一个状态

示例：7 状态 DFA 经划分法 $\to$ 5 状态最小化 DFA；3 状态 DFA 可 $\to$ 2 状态。

重点 划分法初始划分为终态集和非终态集，逐步细化至不动点。

完整流程：RE $\to$ NFA $\to$ DFA $\to$ 最小化 DFA。

DFA 设计典型例题

例 1：含 “001” 的二进制串

设计 DFA，识别所有含子串 “001” 的二进制串。

思路：记录已匹配到 “001” 的前缀长度，分为 4 个状态：

• $S_0$（初态）：尚未匹配任何 “001” 前缀（或已重置）
• $S_1$：已匹配到 “0”
• $S_2$：已匹配到 “00”
• $S_3$（终态）：已匹配到 “001”，此后任意字符均接受

状态转移：

状态	输入 0	输入 1
$S_0$	$S_1$（匹配到第一个0）	$S_0$（未匹配）
$S_1$	$S_2$（匹配到00）	$S_0$（1打断，重置）
$S_2$	$S_2$（继续等1）	$S_3$（匹配到001）
$S_3$	$S_3$（已匹配）	$S_3$（已匹配）

重点 DFA 设计题需根据识别目标设计状态含义，确定转移关系后画状态图。

例 2：不含 “00” 的二进制串

$\Sigma =\{0,1\}$，不含连续两个 0 的串。

• $S_0$（初态/终态）：末尾为 1（或空串）
• $S_1$（终态）：末尾为 0

状态	0	1
$S_0$	$S_1$（出现0）	$S_0$（末尾1）
$S_1$	死状态（连续0，拒绝）	$S_0$（末尾变1）