---
title: 编译原理:NFA转DFA
abbrlink: 51944
date: "2025-03-25 19:18:37"
updated: "2025-07-04 18:44:32"
desc: 不知道写点什么,所以记一下,以防~~失忆~~
categories:
    - 学校学习
tags:
    - 学习
    - 记录
    - 编译原理
---

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

:::ai

本文内容含AI生成内容

:::

## DFA

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

### 定义

一个 DFA 可以用一个五元组 $(Q, \Sigma, \delta, q_0, F)$ 来表示,其中：

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

<!--more-->

### 工作原理

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

### 示例

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

```plaintext
+---0---+
    |       |
    v       |
q0 --1--> q1 --0--> q2
 ^         |       |
 |         +---1---+
 |
 +---0,1---+
```

这里,$Q = \{q_0, q_1, q_2\}$,$\Sigma = \{0, 1\}$,$q_0$ 是初始状态,$F = \{q_2\}$。状态转移函数 $\delta$ 可以表示为：

- $\delta(q_0, 0) = q_0$
- $\delta(q_0, 1) = q_1$
- $\delta(q_1, 0) = q_2$
- $\delta(q_1, 1) = q_1$
- $\delta(q_2, 0) = q_0$
- $\delta(q_2, 1) = q_1$

## NFA

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

### 定义

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

### 工作原理

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

### 示例

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

```plaintext
+---0---+
    |       |
    v       |
q0 --0,1--> q0 --0--> q1 --1--> q2
             ^         |
             |         +---0,1---+
             +---0,1---+
```

这里,$Q = \{q_0, q_1, q_2\}$,$\Sigma = \{0, 1\}$,$q_0$ 是初始状态,$F = \{q_2\}$。状态转移函数 $\delta$ 包含了一些多值转移和 $\epsilon$ 转移(这里没有 $\epsilon$ 转移示例)。

## NFA 转 DFA 步骤

### 步骤 1：确定初始状态

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

### 步骤 2：状态转移计算

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

### 步骤 3：接受状态确定

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

### 步骤 4：重复步骤 2 和 3

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

### 示例

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

| 状态  | 0              | 1         | $\epsilon$ |
| ----- | -------------- | --------- | ---------- |
| $q_0$ | $\{q_0, q_1\}$ | $\{q_0\}$ | $\{\}$     |
| $q_1$ | $\{\}$         | $\{q_2\}$ | $\{\}$     |
| $q_2$ | $\{\}$         | $\{\}$    | $\{\}$     |

初始状态为 $q_0$,接受状态为 $q_2$。

- **初始状态**：$\epsilon\text{-closure}(q_0) = \{q_0\}$,所以 DFA 的初始状态为 $\{q_0\}$。
- **状态转移计算**：
    - 对于状态 $\{q_0\}$,$\delta'(\{q_0\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0)) = \epsilon\text{-closure}(\{q_0, q_1\}) = \{q_0, q_1\}$。
    - $\delta'(\{q_0\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1)) = \epsilon\text{-closure}(\{q_0\}) = \{q_0\}$。
    - 对于状态 $\{q_0, q_1\}$,$\delta'(\{q_0, q_1\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0) \cup \delta(q_1, 0)) = \epsilon\text{-closure}(\{q_0, q_1\} \cup \{\}) = \{q_0, q_1\}$。
    - $\delta'(\{q_0, q_1\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1) \cup \delta(q_1, 1)) = \epsilon\text{-closure}(\{q_0\} \cup \{q_2\}) = \{q_0, q_2\}$。
    - 对于状态 $\{q_0, q_2\}$,$\delta'(\{q_0, q_2\}, 0) = \epsilon\text{-closure}(\delta(q_0, 0) \cup \delta(q_2, 0)) = \epsilon\text{-closure}(\{q_0, q_1\} \cup \{\}) = \{q_0, q_1\}$。
    - $\delta'(\{q_0, q_2\}, 1) = \epsilon\text{-closure}(\delta(q_0, 1) \cup \delta(q_2, 1)) = \epsilon\text{-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。


---

**作者：**xingwangzhe

**本文链接：**[https://xingwangzhe.fun/posts/51944/](https://xingwangzhe.fun/posts/51944/)

本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。