[形式语言与自动机] DFA确定有穷自动机 - Alkaid114

801 字

4 分钟

[形式语言与自动机] DFA确定有穷自动机

2026-05-30

形式语言与自动机

形式语言与自动机

确定有穷自动机的定义#

确定有穷自动机（DFA）是一个五元组：

$A = (Q, \Sigma, \delta, q_0, F)$

其中：

$Q$ 是一个有限的状态集合
$\Sigma$ 是一个有限的输入符号集合（字母表）
$\delta: Q \times \Sigma \to Q$ 是状态转移函数，定义了在给定状态和输入符号的情况下，自动机如何转移到下一个状态
$q_0 \in Q$ 是初始状态
$F \subseteq Q$ 是终结状态集或接受状态集合

条件#

转移是确定且唯一的：对于每个状态 $q \in Q$ 和每个输入符号 $a \in \Sigma$ ，转移函数 $\delta(q, a)$ 定义了一个唯一的下一个状态
DFA在任何时候只能处于一个状态
DFA接受一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个接受状态上
DFA拒绝一个字符串，如果从初始状态出发，按照输入字符串的符号进行状态转移，最终停在一个非接受状态上
DFA不能有ε-转移，即不能在没有输入符号的情况下进行状态转移

DFA最小化#

设有以下DFA：

状态	0	1
$\rightarrow q_0$	$q_1$	$q_2$
$q_1$	$q_3$	$q_4$
$q_2$	$q_3$	$q_4$
$\ast q_3$	$q_3$	$q_3$
$\ast q_4$	$q_4$	$q_4$

Moore算法(填表法，推荐使用)#

接受状态有 $q_3, q_4$ ，非接受状态有 $q_0, q_1, q_2$

首先需要得到所有无序状态对，即所有状态两两组合的集合，因此按如下所示画表格：

横轴没有 $q_0$ ，纵轴没有 $q_4$ ，这样正好错开( $(q_n,q_n)$ 没有用)，当然都写上也是可以的，只是为了省空间

	$q_1$	$q_2$	$q_3$	$q_4$
$q_0$
$q_1$
$q_2$
$q_3$

首轮标记#

只要状态对里两个状态不是相同类型的状态（一个是接受状态，一个是非接受状态），就标记为不同，标记为X，即：

只关注 $(q_n,q_m), n < m$ ，因此只标记上三角部分

	$q_1$	$q_2$	$q_3$	$q_4$
$q_0$			X	X
$q_1$			X	X
$q_2$			X	X
$q_3$

迭代#

检查尚未被X标记的状态对，对其尝试每个输入符号，检查要转移到的下一状态属于的状态对是否已被X标记，如果是，则当前状态对也标记为X，否则不标记。

还剩 $(q_0,q_1), (q_0,q_2), (q_1,q_2), (q_3,q_4)$ ，检查：

$(q_0,q_1)$ ，输入0转移到 $(q_1,q_3)$ ，已标记为X，因此标记 $(q_0,q_1)$ 为X，无需再试1
$(q_0,q_2)$ ，输入0转移到 $(q_1,q_3)$ ，已标记为X，因此标记 $(q_0,q_2)$ 为X
$(q_1,q_2)$ ，输入0转移到 $(q_3,q_3)$ ，未标记，输入1转移到 $(q_4,q_4)$ ，未标记，因此不标记
$(q_3,q_4)$ ，输入0转移到 $(q_3,q_4)$ ，未标记，输入1转移到 $(q_3,q_4)$ ，未标记，因此不标记

	$q_1$	$q_2$	$q_3$	$q_4$
$q_0$	X	X	X	X
$q_1$			X	X
$q_2$			X	X
$q_3$

再次迭代：

还剩 $(q_1,q_2), (q_3,q_4)$ ，检查：

$(q_1,q_2)$ ，输入0转移到 $(q_3,q_3)$ ，未标记，输入1转移到 $(q_4,q_4)$ ，未标记，因此不标记
$(q_3,q_4)$ ，输入0转移到 $(q_3,q_4)$ ，未标记，输入1转移到 $(q_3,q_4)$ ，未标记，因此不标记

转移到的都是自身，迭代完成

最终所有没被画X的状态对是可合并的等价状态

空白的有 $(q_1,q_2), (q_3,q_4)$ ，因此可以合并为两个状态，最终得到最小化DFA：

状态	0	1
$\rightarrow q_0$	$\{q_1, q_2 \}$	$\{q_3, q_4\}$
$\ast \{q_1, q_2\}$	$\{q_3, q_4\}$	$\{q_3, q_4\}$
$\ast \{q_3, q_4\}$	$\{q_3, q_4\}$	$\{q_3, q_4\}$

划分法#

容易错，不写了

[形式语言与自动机] DFA确定有穷自动机

https://alkaid114.github.io/posts/automata/dfa/

作者

Alkaid114

发布于

2026-05-30

许可协议

CC BY-NC-SA 4.0

[形式语言与自动机] NFA非确定有穷自动机

[人工智能数学基础] 向量&矩阵求导

确定有穷自动机的定义

Moore算法(填表法，推荐使用)