有穷自动机

分为两种，确定性有穷自动机（DFA）和非确定性有穷自动机（NFA）。

$\mathrm{NFA}$ 的特征：有以 $ϵ$ 边转换的状态；对于每一个状态 $s$ 和输入字符 $a$ ，都有唯一的转换。

$\mathrm{DFA}$ 较易实现。因此我们考虑将 $\mathrm{NFA}$ 转换为 $\mathrm{DFA}$。

对于有穷自动机更详细的内容，可以参考这里。

NFA 转换为 DFA（子集构造法）

输入：一个 $\mathrm{NFA}$，记作 $N$。

输出：一个 $\mathrm{DFA}$，记作 $D$。

有如下三个操作，其中，$s$ 为 $N$ 中的单个状态，而 $T$ 为 $N$ 中的一个状态集。

操作	描述
$ϵ-closure(s)$	能从 $\mathrm{NFA}$ 的状态 $s$ 开始只通过 $ϵ$ 转换到达的 $\mathrm{NFA}$ 状态集合。
$ϵ-closure(T)$	能够从 $T$ 中某个 $\mathrm{NFA}$ 状态 $s$ 开始只通过 $ϵ$ 转换到达的 $\mathrm{NFA}$ 状态集合，即 $\bigcup _{s\in T}ϵ-closure(s)$。
$move(T,a)$	能从 $T$ 中某个状态，通过输入字符 $a$ 转换到的所有状态的集合。

大致的算法流程如下：

1. 建立一个容器，存放 $D$ 的状态和转换，分别记为 $D_{states}$ 和 $D_{trans}$​​​。
2. 令 $ϵ-closure(s_0)$ 加入 $D_{states}$ ，且它未加标记。其中，$ s_0$ 是 $N$ 的起始状态。
3. 从 $D_{states}$ 取出一个未标记的状态 $T$ ，将其加上标记。并对于字母表中的每一个输入符号 $a$ ，令 $U=ϵ-closure(move(T,a))$，然后再令 $D_{trans}[T,a]=U$，加入 $D_{trans}$ 中。对于每一个产生的 $U$， 如果它不在 $D_{states}$ 之中，将其加入并不加标记。
4. 重复 3 的操作，直到 $D_{states}$ 中所有状态均被标记。

正则表达式转换为 $\mathrm{NFA}$​

注意：计算 $N(s^{\ast })$ 时，不能直接在 $N(s)$ 的起始状态和接受状态上面连一条 $ϵ$ 边。

$\mathrm{DFA}$ 最小化

初始分划：将接受状态划分出来。

在每一个分划中，遍历字母表，尝试找到能将该划分区分成多个的输入字符（串）。重复这一操作直到不能继续划分，这时，每一个划分中的状态对于任意字符串的行为均相同。将这些划分作为新 $\mathrm{DFA}$ 的状态，这一 $\mathrm{DFA}$​ 就是最小的。