NFA 到 DFA 的转换
学习目标
通过本集的学习，你将能够：
- 掌握子集构造法
- 理解 ε-闭包
- 学会构造转换表
- 完成示例演练
1. 为什么需要将 NFA 转换为 DFA？
1.1 NFA 的缺点
NFA 的问题：
- 不确定性：对于同一输入可能有多个状态选择
- 需要处理 ε 转移，增加了复杂性
- 运行时需要跟踪多个可能的状态
- 实现效率较低
DFA 的优点：
- 确定性：每个状态对每个输入只有一个转移
- 没有 ε 转移
- 运行时只需要跟踪一个状态
- 实现效率高1.2 转换的意义
转换的好处：
1. 提高执行效率
2. 简化实现复杂度
3. 为后续的 DFA 最小化做准备
4. 使自动机更易于理解和分析2. 子集构造法
2.1 基本思想
子集构造法（Subset Construction）是一种将 NFA 转换为 DFA 的算法。
核心思想：
- DFA 的每个状态对应 NFA 的一个状态集合
- 这个状态集合表示 NFA 在处理相同输入时可能处于的所有状态
- 通过 ε-闭包处理 ε 转移
- 通过 move 操作处理输入字符转移2.2 构造步骤
构造步骤：
1. 计算 NFA 开始状态的 ε-闭包，作为 DFA 的开始状态
2. 对于每个 DFA 状态（NFA 状态集合）和每个输入符号：
a. 计算该状态集合在输入符号上的 move 操作结果
b. 计算 move 结果的 ε-闭包
c. 如果这个闭包集合不在 DFA 状态中，添加为新的 DFA 状态
d. 添加从当前 DFA 状态到新 DFA 状态的转移
3. 重复步骤 2，直到没有新的 DFA 状态产生
4. DFA 的接受状态是包含至少一个 NFA 接受状态的状态集合3. ε-闭包
3.1 什么是 ε-闭包？
ε-闭包（Epsilon Closure）是一个状态集合，包含从给定状态通过零个或多个 ε 转移可以到达的所有状态。
ε-闭包的定义：
对于状态集合 S，ε-闭包(S) 是包含：
1. S 中的所有状态
2. 从 S 中的状态通过任意数量的 ε 转移可以到达的所有状态3.2 计算 ε-闭包
计算方法（使用广度优先搜索）：
1. 初始化结果集合为 S
2. 使用队列来处理状态
3. 将 S 中的所有状态加入队列
4. 对于队列中的每个状态 q：
a. 找到所有通过 ε 转移从 q 可达的状态
b. 对于每个这样的状态 r：
i. 如果 r 不在结果集合中，添加到结果集合和队列
5. 当队列为空时，返回结果集合3.3 代码实现
def epsilon_closure(nfa, states):
"""计算状态集合的 ε-闭包"""
closure = set(states)
queue = list(states)
while queue:
state = queue.pop(0)
if state in nfa.transitions and 'ε' in nfa.transitions[state]:
for next_state in nfa.transitions[state]['ε']:
if next_state not in closure:
closure.add(next_state)
queue.append(next_state)
return closure4. move 操作
4.1 什么是 move 操作？
move 操作是指对于一个状态集合和一个输入符号，计算所有通过该输入符号可以到达的状态集合。
move 操作的定义：
move(S, a) = { q | 存在 p ∈ S，使得 q ∈ δ(p, a) }
其中：
S 是 NFA 的状态集合
δ 是 NFA 的转移函数
a 是输入符号4.2 代码实现
def move(nfa, states, symbol):
"""计算状态集合在输入符号上的 move 操作"""
result = set()
for state in states:
if state in nfa.transitions and symbol in nfa.transitions[state]:
result.update(nfa.transitions[state][symbol])
return result5. 转换表构造
5.1 转换表的结构
转换表记录了 DFA 的状态转移关系。
转换表的结构：
状态\输入 | a | b | ...
---------|-----|-----|-----
S0 | S1 | S2 | ...
S1 | S3 | S4 | ...
S2 | S5 | S6 | ...
... | ... | ... | ...
其中：
- S0, S1, S2 等是 DFA 的状态（对应 NFA 的状态集合）
- 每个单元格表示从当前状态在对应输入下转移到的下一个状态5.2 构造转换表的步骤
构造步骤：
1. 初始化 DFA 状态集合，包含开始状态的 ε-闭包
2. 对每个未处理的 DFA 状态：
a. 对每个输入符号：
i. 计算 move 操作
ii. 计算 ε-闭包
iii. 检查是否是新状态
iv. 添加到转换表
3. 标记包含 NFA 接受状态的 DFA 状态为接受状态6. 示例演练
6.1 示例 NFA
我们使用一个简单的 NFA 来演示转换过程：
NFA 状态图：
┌───┐
│ ε │
└─┬─┘
│
▼
┌───┐ ┌───┐ ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘ └───┘ └───┘
│ │a │ε
│ │ │
│ │ ▼
│ ε │ ┌───┐
└──┐ │ │ q3│
│ │ └───┘
│ │ ↑
│ └─────┘ ε
│ │
└─────────┘ ε
NFA 定义：
- 状态：{q0, q1, q2, q3}
- 输入字母表：{a}
- 转移函数：
δ(q0, ε) = {q1, q3}
δ(q1, a) = {q2}
δ(q2, ε) = {q3}
δ(q3, ε) = {q1}
- 开始状态：q0
- 接受状态：{q3}6.2 转换过程
步骤 1：计算开始状态的 ε-闭包
开始状态 q0 的 ε-闭包：
ε-closure({q0}) = {q0, q1, q3}
这将成为 DFA 的开始状态，记为 S0步骤 2：处理 DFA 状态 S0
处理 S0 = {q0, q1, q3} 对输入 a：
1. 计算 move(S0, a)：
move({q0, q1, q3}, a) = {q2} （只有 q1 有 a 转移）
2. 计算 ε-closure({q2})：
ε-closure({q2}) = {q2, q3, q1}
3. 这个集合不在 DFA 状态中，添加为 S1
4. 添加转移 S0 --a--> S1步骤 3：处理 DFA 状态 S1
处理 S1 = {q1, q2, q3} 对输入 a：
1. 计算 move(S1, a)：
move({q1, q2, q3}, a) = {q2}
2. 计算 ε-closure({q2})：
ε-closure({q2}) = {q2, q3, q1} = S1
3. 这个集合已经是 S1，添加转移 S1 --a--> S1步骤 4：标记接受状态
检查哪些 DFA 状态包含 NFA 的接受状态 q3：
- S0 = {q0, q1, q3} → 包含 q3 → 接受状态
- S1 = {q1, q2, q3} → 包含 q3 → 接受状态6.3 最终的 DFA
DFA 状态图：
┌──────┐ a ┌──────┐
│ S0 │────→│ S1 │
└──────┘ └──────┘
^ │
│ a │ a
└───────────┘
其中：
S0 = {q0, q1, q3} （开始，接受）
S1 = {q1, q2, q3} （接受）
转换表：
状态\输入 | a
---------|----
S0 | S1
S1 | S17. 更复杂的示例
7.1 示例 NFA：识别 a|b
NFA 状态图：
┌───┐
│ ε │
└─┬─┘
│
▼
┌───┐ ┌───┐ ┌───┐
│ q0│─→│ q1│─→│ q2│
└───┘ └───┘ └───┘
│ │a │ε
│ │ │
│ │ ▼
│ ε │ ┌───┐
└──┐ │ │ q5│
│ │ └───┘
▼ │ ↑
┌───┐ │ │
│ q3│─┐ │ │ b
│ │ │
▼ ▼ │
┌───┐ │
│ q4│─────┘
└───┘
开始状态：q0
接受状态：{q5}7.2 转换结果
DFA 状态：
S0 = {q0, q1, q3} （开始）
S1 = {q2, q5} （接受）
S2 = {q4, q5} （接受）
S3 = {q5} （接受）
转换表：
状态\输入 | a | b
---------|-----|----
S0 | S1 | S2
S1 | S3 | S3
S2 | S3 | S3
S3 | S3 | S3
DFA 状态图：
┌──────┐ a ┌──────┐
│ S0 │────→│ S1 │
└──────┘ └──────┘
│ b │ a,b
▼ │
┌──────┐ │
│ S2 │───────┘
└──────┘ │
│ a,b │
▼ │
┌──────┐◄──────┘
│ S3 │
└──────┘8. 实用案例
8.1 案例 1：用 Python 实现子集构造法
class DFA:
def __init__(self, states, alphabet, transitions, start_state, accept_states):
self.states = states
self.alphabet = alphabet
self.transitions = transitions
self.start_state = start_state
self.accept_states = accept_states
def nfa_to_dfa(nfa):
"""将 NFA 转换为 DFA"""
# 辅助函数：计算 ε-闭包
def epsilon_closure(states):
closure = set(states)
queue = list(states)
while queue:
state = queue.pop(0)
if state in nfa.transitions and 'ε' in nfa.transitions[state]:
for next_state in nfa.transitions[state]['ε']:
if next_state not in closure:
closure.add(next_state)
queue.append(next_state)
return frozenset(closure) # 使用 frozenset 作为字典键
# 辅助函数：计算 move 操作
def move(states, symbol):
result = set()
for state in states:
if state in nfa.transitions and symbol in nfa.transitions[state]:
result.update(nfa.transitions[state][symbol])
return result
# 初始化
dfa_states = set()
dfa_transitions = {}
dfa_start = epsilon_closure({nfa.start_state})
dfa_states.add(dfa_start)
# 使用队列处理未处理的 DFA 状态
queue = [dfa_start]
while queue:
current = queue.pop(0)
dfa_transitions[current] = {}
for symbol in nfa.alphabet:
# 计算 move 和 ε-闭包
moved = move(current, symbol)
closure = epsilon_closure(moved)
# 添加新状态
if closure not in dfa_states:
dfa_states.add(closure)
queue.append(closure)
dfa_transitions[current][symbol] = closure
# 确定接受状态
dfa_accept = set()
for state in dfa_states:
if any(s in nfa.accept_states for s in state):
dfa_accept.add(state)
# 为了方便，我们可以给 DFA 状态起个名字
state_map = {}
for i, state in enumerate(dfa_states):
state_map[state] = f'S{i}'
# 重命名后的 DFA
renamed_states = set(state_map.values())
renamed_transitions = {}
for state, trans in dfa_transitions.items():
renamed_trans = {}
for symbol, next_state in trans.items():
renamed_trans[symbol] = state_map[next_state]
renamed_states.add(state_map[state])
renamed_transitions[state_map[state]] = renamed_trans
renamed_start = state_map[dfa_start]
renamed_accept = {state_map[s] for s in dfa_accept}
return DFA(
renamed_states,
nfa.alphabet,
renamed_transitions,
renamed_start,
renamed_accept
)
# 测试
# 假设有一个 NFA 对象
# dfa = nfa_to_dfa(nfa)
# print(dfa.states)
# print(dfa.transitions)
# print(dfa.start_state)
# print(dfa.accept_states)8.2 案例 2：简化 DFA 表示
def print_dfa(dfa):
"""打印 DFA 的转换表"""
print("DFA 转换表:")
print("状态\输入", end="")
for symbol in dfa.alphabet:
print(f" | {symbol}", end="")
print()
print("---------" + "|-----" * len(dfa.alphabet))
for state in dfa.states:
print(f" {state}", end="")
for symbol in dfa.alphabet:
next_state = dfa.transitions.get(state, {}).get(symbol, "-")
print(f" | {next_state}", end="")
print()
print(f"\n开始状态: {dfa.start_state}")
print(f"接受状态: {dfa.accept_states}")
# 使用示例
# print_dfa(dfa)9. 自测问题
- 为什么需要将 NFA 转换为 DFA？
- 什么是子集构造法？
- 什么是 ε-闭包？
- 子集构造法的基本步骤是什么？
- DFA 的状态与 NFA 的状态有什么关系？
10. 下集预告
下一集我们将学习 DFA 的最小化！
参考资料
- 《编译原理》（龙书）
- 《自动机理论、语言和计算导论》