通过前面对于词法自动生成部分的学习，我们已经掌握了如何从源码生成到 DFA
那么为什么要对 DFA 进行最小化处理呢？
下面给出一个例子：
如下是我们之前写出的 a (b|c)* 的 NFA：
它可以对应转换成如下的 DFA：
在上面的 DFA 中非接受状态和接受状态是不能够合并的，因为如果合并，就会接受一个 $\epsilon$ 串，这是明显不正确的。但是如果同样是接受状态或者同样是非接受状态的话就有可能。例如可以将 $q_2$ 和 $q_3$ 进行合并，得到一个新的接受状态 $q_4$。得到新的 DFA，如下：
之后，我们还可以再对 $q_1$ 和 $q_4$ 进行融合得到 $q_5$
这就是最终的状态最少的 DFA
最小化得到状态最少的 DFA 的好处在于，因为 DFA 最后的代码实现是在作为内部的一个数据结构表示，如果状态和边越少，则它占用的计算资源（内存、cache）会更少 ，可以提高算法的运行效率和速度
Hopcroft 算法展开目录
- //基于等价类的思想
- split(S)
- foreach(character c)
- if(c can split s)
- split s into T1, ..., Tk
-
- hopcroft()
- split all nodes into N, A
- while(set is still changes)
- split(s)
$q_1,q_2,q_3$ 都有对状态 a 的转移，但是 $q_1$ 和 $q_2$ 转移到了同样的一个状态 S2, $q_3$ 转移到了 S3。所以 $q_1$,$q_2$ 可以看做一组，因为它们对 a 的行为是一致的，都到了 S2。$q_3$ 单独一组。所以 a 这个字符将 S1 切为了两个子集。这就是等价类的思想
Hopsroft 算法就是先根据非终结状态与终结状态将所有的节点分为 N 和 A 两大类。 N 为非终结状态，A 为终结状态，之后再对每一组运用基于等价类实现的切割算法
举个例子展开目录
对于之前给出的 DFA 的例子，我们首先将其切分为 N 和 A, $N=\{q_0\}$，$A=\{q_1, q_2, q_3\}$
在 A 中，字符 b,c 的状态转移，每个节点最后得到的都还是 A 这个状态，无法对 $q_1,q_2,q_3$ 进行区分。所以就将这三个节点融合为一个新的节点 $q_4$
再给一个例子展开目录
$$ \begin{align*} N&=\{q_0, q_1, q_2, q_4\}\\ A&=\{q_3, q_5\} \end{align*} $$
在 N 中 $q_0$ 和 $q_1$ 在接受 e 的条件下最终得到的状态还是在 N 的内部，但是 $q_3$ 和 $q_4$ 接受 e 的条件下得到的状态是 A。所以可以将其根据 e 拆分成 {$q_0,q_1$},{$q_2,q_4$},{$q_3, q_5$}
对于 $q_2$ 和 $q_4$ 都可以接受 e，而且最终达到的状态一致，所以不能再进行切分
$q_0$ 和 $q_1$ 在接受 e 的时候，$q_0$ 最终还是在 {$q_0, q_1$} 这个状态的结合中，$q_1$ 却会落在 {$q_2,q_4$} 的状态中，所以可以将 $q_0$ 和 $q_1$ 分为 {$q_0$},{$q_1$}
因此最终的状态集合为 $\{\{q_0\},\{q_1\},\{q_2,q_4\},\{q_3,q_5\}\}$
