2 自动机

NFA

一个数学模型，包括：

（Ⅰ）有限的状态集合 $S$ ；

（Ⅱ）输入符号集合 $\Sigma$ （不考虑 $\varepsilon\in \Sigma$ ）；

（Ⅲ）转换函数 $\text{move}:S\times(\Sigma\cup\{\varepsilon\})→\mathscr{P}(S)$ ；

这里写的有点逆天，实际上就是指 move 函数接收两个参数，表示当前位于状态 $S_i$ ，当接收到某个字符 $i\in\Sigma\cup\{\varepsilon\}$ 时会跳转到什么状态（因为可能有很多个，所以是 $S$ 的幂集的一个元素）。

（Ⅳ）唯一的一个开始状态 $s_0$ ；

（Ⅴ）接受（终止）状态集合 $F\subseteq S$ 。

相当于一个矩阵，行是 $S$ 的枚举 $S_i$ ，列是 $\Sigma\cup\{\varepsilon\}$ 的枚举 $c_j$ ，每个元素是 $\text{move}(S_i,c_j)$ 。

NFA 接受一个串 $x$ ，当且仅当 NFA 中存在从开始状态到某个接受状态的路径，此路径上的标记拼成 $x$ 。

DFA 是 NFA 的一个特殊情形，特殊就特殊在

（Ⅰ）任何状态下没有 $\varepsilon$ 转换；

（Ⅱ）转换函数变为 $\text{move}:S\times\Sigma→S$ ，并且可以是一个部分函数。

本文阅读量