DFA 的最小化
学习目标
通过本集的学习，你将能够：
- 理解为什么需要最小化 DFA
- 掌握 Hopcroft 算法
- 理解可区分状态
- 完成示例演练
1. 为什么需要最小化？
1.1 最小化的好处
最小化 DFA 的原因：
1. **减少状态数**：降低存储空间需求
2. **提高执行效率**：减少状态转移的查找时间
3. **简化自动机**：使自动机更易于理解和分析
4. **优化后续处理**：为代码生成等后续步骤做准备
具体表现：
- 内存使用减少
- 运行速度加快
- 代码体积减小
- 维护成本降低1.2 最小化的定义
最小 DFA 的定义：
- 状态数最少的等价 DFA
- 对于任何等价的 DFA，其状态数不小于最小 DFA
- 最小 DFA 在同构意义下是唯一的
等价的含义：
两个 DFA 识别相同的语言1.3 示例对比
原始 DFA（4 个状态）：
┌──────┐ a ┌──────┐
│ S0 │────→│ S1 │
└──────┘ └──────┘
│ b │ a,b
▼ │
┌──────┐ │
│ S2 │───────┘
└──────┘ │
│ a,b │
▼ │
┌──────┐◄──────┘
│ S3 │
└──────┘
最小化后（2 个状态）：
┌──────┐ a ┌──────┐
│ A │────→│ B │
└──────┘ └──────┘
│ b │ a,b
└───────────┘2. 可区分状态
2.1 基本概念
可区分状态（Distinguishable States）：
- 如果存在一个输入字符串，使得从状态 p 和 q 出发，处理该字符串后，一个进入接受状态，另一个进入非接受状态，则 p 和 q 是可区分的
不可区分状态（Indistinguishable States）：
- 如果对于所有输入字符串，从状态 p 和 q 出发，处理该字符串后，要么都进入接受状态，要么都进入非接受状态，则 p 和 q 是不可区分的
不可区分状态可以合并为一个状态2.2 初始划分
初始划分步骤：
1. 将所有状态分为两个集合：
- F：接受状态集合
- Q-F：非接受状态集合
2. 这是最基本的划分，因为接受状态和非接受状态显然是可区分的
3. 然后递归地细化这个划分，直到不能再细化为止2.3 细化划分
细化过程：
1. 对于每个划分块 B 和每个输入符号 a：
a. 计算 B 中每个状态在输入 a 下的后继状态所在的块
b. 如果这些后继状态所在的块不完全相同，则需要将 B 分割成多个子块
c. 每个子块中的状态在输入 a 下的后继状态都在同一个块中
2. 重复这个过程，直到没有块可以被分割3. Hopcroft 算法
3.1 算法概述
Hopcroft 算法是一种高效的 DFA 最小化算法，由 John Hopcroft 在 1971 年提出。
Hopcroft 算法的特点：
- 时间复杂度：O(n log n)，其中 n 是状态数
- 空间复杂度：O(n)
- 是目前已知的最快的 DFA 最小化算法
- 采用贪心策略，优先处理较小的划分块3.2 算法步骤
算法步骤：
1. 初始化划分：
- P = {F, Q-F}（F 是接受状态集合）
- W = {F, Q-F}（工作集合，包含需要处理的块）
2. 当 W 不为空时：
a. 从 W 中取出一个块 A
b. 对于每个输入符号 a：
i. 计算所有状态 p，使得 move(p, a) ∈ A（记为 P_a）
ii. 对于每个块 B ∈ P：
- 计算 B ∩ P_a 和 B - P_a
- 如果两者都非空：
* 将 B 从 P 中移除
* 将 B ∩ P_a 和 B - P_a 添加到 P 中
* 如果 B 在 W 中：
· 将 B 从 W 中移除
· 将 B ∩ P_a 和 B - P_a 添加到 W 中
* 否则：
· 将较小的块添加到 W 中
3. 最终的 P 中的每个块对应最小 DFA 的一个状态3.3 算法演示
演示 Hopcroft 算法的执行过程：
初始状态：
P = {{非接受状态}, {接受状态}}
W = {{非接受状态}, {接受状态}}
处理过程：
- 取出块 A
- 对每个输入符号 a
- 计算 P_a
- 细化划分
- 更新工作集合4. 示例演练
4.1 示例 DFA
我们使用一个简单的 DFA 来演示最小化过程：
DFA 定义：
- 状态：{S0, S1, S2, S3}
- 输入字母表：{a, b}
- 转移函数：
δ(S0, a) = S1
δ(S0, b) = S2
δ(S1, a) = S3
δ(S1, b) = S3
δ(S2, a) = S3
δ(S2, b) = S3
δ(S3, a) = S3
δ(S3, b) = S3
- 开始状态：S0
- 接受状态：{S3}
状态图：
┌──────┐ a ┌──────┐
│ S0 │────→│ S1 │
└──────┘ └──────┘
│ b │ a,b
▼ │
┌──────┐ │
│ S2 │───────┘
└──────┘ │
│ a,b │
▼ │
┌──────┐◄──────┘
│ S3 │
└──────┘4.2 最小化过程
步骤 1：初始划分
初始划分 P0：
- 非接受状态：{S0, S1, S2}
- 接受状态：{S3}
P = {{S0, S1, S2}, {S3}}
W = {{S0, S1, S2}, {S3}}步骤 2：处理块 {S3}
取出 A = {S3}
对输入 a：
P_a = {p | δ(p, a) ∈ {S3}} = {S1, S2, S3}
对于块 B = {S0, S1, S2}：
B ∩ P_a = {S1, S2}
B - P_a = {S0}
需要分割 B：
将 {S0, S1, S2} 替换为 {S0}, {S1, S2}
更新 P：{{S0}, {S1, S2}, {S3}}
更新 W：{{S0, S1, S2} 已处理，添加 {S0}, {S1, S2}}步骤 3：处理块 {S0}
取出 A = {S0}
对输入 a：
P_a = {p | δ(p, a) ∈ {S0}} = ∅
没有块需要分割
对输入 b：
P_a = {p | δ(p, b) ∈ {S0}} = ∅
没有块需要分割步骤 4：处理块 {S1, S2}
取出 A = {S1, S2}
对输入 a：
P_a = {p | δ(p, a) ∈ {S1, S2}} = {S0}
对于块 B = {S0}：
B ∩ P_a = {S0}
B - P_a = ∅
不需要分割
对输入 b：
P_a = {p | δ(p, b) ∈ {S1, S2}} = {S0}
同样不需要分割步骤 5：最终划分
最终划分 P：{{S0}, {S1, S2}, {S3}}
这意味着：
- S0 是一个独立状态
- S1 和 S2 可以合并为一个状态
- S3 是一个独立状态4.3 构造最小 DFA
构造最小 DFA：
1. 状态重命名：
A = {S0}（开始状态）
B = {S1, S2}
C = {S3}（接受状态）
2. 构造转移函数：
δ(A, a) = B （因为 δ(S0, a) = S1 ∈ B）
δ(A, b) = B （因为 δ(S0, b) = S2 ∈ B）
δ(B, a) = C （因为 δ(S1, a) = S3 ∈ C，δ(S2, a) = S3 ∈ C）
δ(B, b) = C （因为 δ(S1, b) = S3 ∈ C，δ(S2, b) = S3 ∈ C）
δ(C, a) = C （因为 δ(S3, a) = S3 ∈ C）
δ(C, b) = C （因为 δ(S3, b) = S3 ∈ C）
3. 最小 DFA 状态图：
┌──────┐ a ┌──────┐ a,b ┌──────┐
│ A │────→│ B │──────→│ C │
└──────┘ b └──────┘ └──────┘
│ ↑a,b
└──────────────────────────┘3. 实用算法实现
3.1 表格填充法
表格填充法是一种直观的 DFA 最小化算法，适合手动计算。
算法步骤：
1. 创建一个 n×n 的表格，n 是状态数
2. 初始标记：对于任何 i < j，如果一个状态是接受状态，另一个不是，则标记为可区分
3. 迭代标记：对于每个未标记的对 (p, q) 和每个输入符号 a：
a. 计算 r = δ(p, a), s = δ(q, a)
b. 如果 (r, s) 已经被标记为可区分，则标记 (p, q) 为可区分
4. 重复步骤 3，直到没有新的标记
5. 未标记的状态对是不可区分的，可以合并3.2 代码实现
def minimize_dfa(dfa):
"""使用 Hopcroft 算法最小化 DFA"""
# 获取所有状态
states = list(dfa.states)
n = len(states)
# 初始化划分
# 第一组：非接受状态，第二组：接受状态
partition = []
non_accept = [s for s in states if s not in dfa.accept_states]
accept = [s for s in states if s in dfa.accept_states]
if non_accept:
partition.append(set(non_accept))
if accept:
partition.append(set(accept))
# 工作集合
worklist = []
if non_accept:
worklist.append(set(non_accept))
if accept:
worklist.append(set(accept))
# 输入字母表
alphabet = list(dfa.alphabet)
# Hopcroft 算法主循环
while worklist:
A = worklist.pop(0)
for a in alphabet:
# 计算 P_a：所有状态 p 使得 δ(p, a) ∈ A
P_a = set()
for s in states:
if s in dfa.transitions and a in dfa.transitions[s]:
next_state = dfa.transitions[s][a]
if next_state in A:
P_a.add(s)
# 遍历当前划分中的每个块
new_partition = []
for B in partition:
# 计算 B ∩ P_a 和 B - P_a
B_intersect = B.intersection(P_a)
B_minus = B.difference(P_a)
if B_intersect and B_minus:
# 需要分割 B
new_partition.append(B_intersect)
new_partition.append(B_minus)
# 更新工作列表
if B in worklist:
worklist.remove(B)
worklist.append(B_intersect)
worklist.append(B_minus)
else:
# 添加较小的块
if len(B_intersect) <= len(B_minus):
worklist.append(B_intersect)
else:
worklist.append(B_minus)
else:
new_partition.append(B)
partition = new_partition
# 构造最小 DFA
# 1. 为每个块创建状态名
state_map = {}
for i, block in enumerate(partition):
state_map[frozenset(block)] = f'Q{i}'
# 2. 确定开始状态
start_block = None
for block in partition:
if dfa.start_state in block:
start_block = frozenset(block)
break
# 3. 确定接受状态
accept_blocks = []
for block in partition:
if any(s in dfa.accept_states for s in block):
accept_blocks.append(frozenset(block))
# 4. 构造转移函数
min_transitions = {}
for block in partition:
block_frozen = frozenset(block)
state_name = state_map[block_frozen]
min_transitions[state_name] = {}
# 取块中的一个代表状态
representative = next(iter(block))
for a in alphabet:
if representative in dfa.transitions and a in dfa.transitions[representative]:
next_state = dfa.transitions[representative][a]
# 找到 next_state 所在的块
for b in partition:
if next_state in b:
next_block = frozenset(b)
min_transitions[state_name][a] = state_map[next_block]
break
# 5. 整理结果
min_states = set(state_map.values())
min_start = state_map[start_block]
min_accept = {state_map[b] for b in accept_blocks}
return {
'states': min_states,
'alphabet': dfa.alphabet,
'transitions': min_transitions,
'start_state': min_start,
'accept_states': min_accept
}
# 测试
# min_dfa = minimize_dfa(dfa)
# print(min_dfa)4. 更复杂的示例
4.1 示例 DFA
DFA 定义：
- 状态：{S0, S1, S2, S3, S4, S5}
- 输入字母表：{a, b}
- 接受状态：{S4, S5}
- 转移函数：
δ(S0, a) = S1, δ(S0, b) = S2
δ(S1, a) = S3, δ(S1, b) = S4
δ(S2, a) = S4, δ(S2, b) = S5
δ(S3, a) = S3, δ(S3, b) = S4
δ(S4, a) = S4, δ(S4, b) = S4
δ(S5, a) = S5, δ(S5, b) = S54.2 最小化过程
初始划分：
非接受：{S0, S1, S2, S3}
接受：{S4, S5}
细化过程：
1. 处理接受状态 {S4, S5}
发现 S4 和 S5 对输入 a 和 b 的转移不同，需要分割
新划分：{S0, S1, S2, S3}, {S4}, {S5}
2. 处理 {S0, S1, S2, S3}
发现 S0、S1、S2、S3 对输入的转移不同，需要进一步分割
新划分：{S0}, {S1}, {S2}, {S3}, {S4}, {S5}
最终最小 DFA 有 6 个状态，说明原始 DFA 已经是最小的5. 自测问题
- 为什么需要最小化 DFA？
- 什么是可区分状态？
- Hopcroft 算法的基本思想是什么？
- 初始划分是如何确定的？
- 最小 DFA 在什么意义下是唯一的？
6. 下集预告
下一集我们将学习 Lex / Flex 工具入门！
参考资料
- 《编译原理》（龙书）
- 《自动机理论、语言和计算导论》
- Hopcroft, J. E. (1971). "An n log n algorithm for minimizing states in a finite automaton"