编译原理:NFA转DFA

发布时间：2025-03-25 19:18:37更新时间：2025-07-04 18:44:32

🕒 阅读时间：10 分钟📝 字数：3632👀 阅读量：Loading...

查看 Markdown 原文

不知道写点什么,所以记一下,以防失忆

:::ai

本文内容含AI生成内容

:::

DFA

确定有限自动机(Deterministic Finite Automaton,DFA)是一种计算模型,常用于模式匹配、词法分析等领域。

定义

一个 DFA 可以用一个五元组 $(Q, Σ, δ, q_{0}, F)$ 来表示,其中：

$Q$ 是一个有限的状态集合。
$Σ$ 是一个有限的输入符号集合。
$δ$ 是状态转移函数,它将 $Q \times Σ$ 映射到 $Q$ 。也就是说,对于当前状态和输入符号,DFA 有唯一的下一个状态。
$q_{0}$ 是初始状态, $q_{0} \in Q$ 。
$F$ 是接受状态集合, $F \subseteq Q$ 。

工作原理

DFA 从初始状态开始,根据输入符号和状态转移函数不断地转移状态。当输入字符串处理完毕后,如果 DFA 处于接受状态集合中的某个状态,则认为该字符串被 DFA 接受；否则,该字符串被拒绝。

示例

假设我们有一个 DFA 用于识别以 01 结尾的二进制字符串,其状态转移图如下：

1
+---0---+
2
    |       |
3
    v       |
4
q0 --1--> q1 --0--> q2
5
 ^         |       |
6
 |         +---1---+
7
 |
8
 +---0,1---+

这里, $Q = {q_{0}, q_{1}, q_{2}}$ , $Σ = {0, 1}$ , $q_{0}$ 是初始状态, $F = {q_{2}}$ 。状态转移函数 $δ$ 可以表示为：

$δ (q_{0}, 0) = q_{0}$
$δ (q_{0}, 1) = q_{1}$
$δ (q_{1}, 0) = q_{2}$
$δ (q_{1}, 1) = q_{1}$
$δ (q_{2}, 0) = q_{0}$
$δ (q_{2}, 1) = q_{1}$

NFA

非确定有限自动机(Non-Deterministic Finite Automaton,NFA)也是一种计算模型,与 DFA 相比,它在状态转移上具有不确定性。

定义

一个 NFA 同样可以用一个五元组 $(Q, Σ, δ, q_{0}, F)$ 来表示,不过状态转移函数 $δ$ 的定义有所不同。这里, $δ$ 将 $Q \times (Σ \cup {ϵ})$ 映射到 $2^{Q}$ ,即对于当前状态和输入符号(可以是 $ϵ$ ,表示空转移),NFA 可能有多个下一个状态。

工作原理

NFA 在处理输入字符串时,对于每个输入符号,它可以同时尝试多个可能的状态转移。如果存在一条从初始状态到某个接受状态的路径,使得沿着该路径处理完整个输入字符串,则认为该字符串被 NFA 接受。

示例

考虑一个 NFA 用于识别包含 01 子串的二进制字符串,其状态转移图如下：

1
+---0---+
2
    |       |
3
    v       |
4
q0 --0,1--> q0 --0--> q1 --1--> q2
5
             ^         |
6
             |         +---0,1---+
7
             +---0,1---+

这里, $Q = {q_{0}, q_{1}, q_{2}}$ , $Σ = {0, 1}$ , $q_{0}$ 是初始状态, $F = {q_{2}}$ 。状态转移函数 $δ$ 包含了一些多值转移和 $ϵ$ 转移(这里没有 $ϵ$ 转移示例)。

NFA 转 DFA 步骤

步骤 1：确定初始状态

对于 NFA 的初始状态 $q_{0}$ ,计算其 $ϵ$ -闭包( $ϵ$ -closure),记为 $C_{0}$ 。 $ϵ$ -闭包是指从某个状态出发,仅通过 $ϵ$ 转移能够到达的所有状态的集合。
将 $C_{0}$ 作为 DFA 的初始状态。

步骤 2：状态转移计算

对于 DFA 中的每个状态(这些状态实际上是 NFA 状态的集合),对于输入符号集合 $Σ$ 中的每个符号 $a$ ,计算该状态在符号 $a$ 下的转移。
具体来说,对于 DFA 的状态 $S$ ,计算 $δ^{'} (S, a) = ϵ -closure (⋃_{q \in S} δ (q, a))$ ,其中 $δ^{'}$ 是 DFA 的状态转移函数。

步骤 3：接受状态确定

如果 DFA 的某个状态 $S$ 包含 NFA 的接受状态集合 $F$ 中的至少一个状态,则将 $S$ 标记为 DFA 的接受状态。

步骤 4：重复步骤 2 和 3

不断重复步骤 2 和 3,直到没有新的 DFA 状态产生为止。

示例

假设我们有一个简单的 NFA,其状态转移表如下：

状态	0	1	$ϵ$
$q_{0}$	${q_{0}, q_{1}}$	${q_{0}}$	${}$
$q_{1}$	${}$	${q_{2}}$	${}$
$q_{2}$	${}$	${}$	${}$

初始状态为 $q_{0}$ ,接受状态为 $q_{2}$ 。

初始状态： $ϵ -closure (q_{0}) = {q_{0}}$ ,所以 DFA 的初始状态为 ${q_{0}}$ 。
状态转移计算：
- 对于状态 ${q_{0}}$ , $δ^{'} ({q_{0}}, 0) = ϵ -closure (δ (q_{0}, 0)) = ϵ -closure ({q_{0}, q_{1}}) = {q_{0}, q_{1}}$ 。
- $δ^{'} ({q_{0}}, 1) = ϵ -closure (δ (q_{0}, 1)) = ϵ -closure ({q_{0}}) = {q_{0}}$ 。
- 对于状态 ${q_{0}, q_{1}}$ , $δ^{'} ({q_{0}, q_{1}}, 0) = ϵ -closure (δ (q_{0}, 0) \cup δ (q_{1}, 0)) = ϵ -closure ({q_{0}, q_{1}} \cup {}) = {q_{0}, q_{1}}$ 。
- $δ^{'} ({q_{0}, q_{1}}, 1) = ϵ -closure (δ (q_{0}, 1) \cup δ (q_{1}, 1)) = ϵ -closure ({q_{0}} \cup {q_{2}}) = {q_{0}, q_{2}}$ 。
- 对于状态 ${q_{0}, q_{2}}$ , $δ^{'} ({q_{0}, q_{2}}, 0) = ϵ -closure (δ (q_{0}, 0) \cup δ (q_{2}, 0)) = ϵ -closure ({q_{0}, q_{1}} \cup {}) = {q_{0}, q_{1}}$ 。
- $δ^{'} ({q_{0}, q_{2}}, 1) = ϵ -closure (δ (q_{0}, 1) \cup δ (q_{2}, 1)) = ϵ -closure ({q_{0}} \cup {}) = {q_{0}}$ 。
接受状态确定：
- 状态 ${q_{0}, q_{2}}$ 包含 NFA 的接受状态 $q_{2}$ ,所以 ${q_{0}, q_{2}}$ 是 DFA 的接受状态。

最终得到的 DFA 状态转移表如下：

状态	0	1
${q_{0}}$	${q_{0}, q_{1}}$	${q_{0}}$
${q_{0}, q_{1}}$	${q_{0}, q_{1}}$	${q_{0}, q_{2}}$
${q_{0}, q_{2}}$	${q_{0}, q_{1}}$	${q_{0}}$

通过以上步骤,我们成功地将 NFA 转换为了 DFA。

编译原理:NFA转DFA

作者：xingwangzhe

本文链接：https://xingwangzhe.fun/posts/51944/

本文采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

DFA

定义

工作原理

示例

NFA

定义

工作原理

示例

NFA 转 DFA 步骤

步骤 1：确定初始状态

步骤 2：状态转移计算

步骤 3：接受状态确定

步骤 4：重复步骤 2 和 3

示例

留言评论