通过前面对于词法自动生成部分的学习，我们已经掌握了如何从源码生成到 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\}\}$
