上一节我们完成了从NFA到DFA的状态机转换，有个问题是状态机并非处于最有状态： 在上图的状态机中，状态6和7其实可以合成一个状态点，本节我们看看如何将这类节点进行合并，使得状态机处于最精简状态(状态4也是终结点，图中有误)。

首先我们把所有节点罗列成下表：

第一步我们先把节点根据是否为终结点分成两组，非终结点为一组，终结点为一组，并给每组设置编号，第一组编号0，第二组编号1： [0,1,2,5]->(0), [3,4,6,7]->(1)

接下来我们分别进入每个分区，分别取出其中两个节点，如果他们接收相同输入，如果跳转的节点在不同分区，那么我们就认为这两个节点不能合成一个点，首先我们看分区0中的点0，它接收D后跳转到2，而节点2位于分区0；分区0中的点1接收D后跳转到节点3，它位于分区1；分区0中节点2接收D后跳转到节点5，后者位于分区0；分区0中节点5接收D后跳转5，后者同样位于分区0，于是我们把分区0中的节点1单独隔离出来形成一个分区： [0,2,5]->(0), [1]->(2), [3,4,6,7]->(1)

接着我们看分区1，分区1中的节点3接收D后没有跳转，节点4接收D后跳转6，后者位于分区1；节点6,7接收D后跳转分区1，因此节点3要从分区1中隔离出来自己形成一个分区： [0,2,5]->(0), [1]->(2), [3]->(3), [4,6,7]->(1)

接下来我们以输入’.‘来看每个分区，在分区0中节点0接收’.‘后跳转1，后者位于分区2；节点2接收’.‘，跳转到节点4，后者位于分区1，节点5接收’.'后跳转到节点1，后者为于分区2，因此我们把节点2从分区0中区分开成为一个新分区： [0,5]->(0), [1]->(2), [3]->(3), [2]->(4), [4,6,7]->(1)

对于只有1个节点的分区我们可以忽略，现在我们看分区1，节点4接收’.‘后没有跳转，节点6接收’.'后没有跳转，节点7接收’.'后也是没有跳转，因此这三个点依然可以属于同一个分区。接下来我们继续返回到分区0，节点0接收D后跳转节点2，后者位于分区4，节点5接收D后跳转到节点5，后者位于分区0，因此我们把点0从分区0拿出来形成一个新分区： [5]->(0), [1]->(2), [3]->(3), [2]->(4),[4,6,7]->(1), [0]->(5) 由此我们把节点4,6,7合并成一个节点，其他分区都只有一个节点，现在我们用分区编号替代每个分区集合中的点，由此得到DFA状态机如下：

下面我们给出算法的步骤描述，首先给出变量声明： c: 当前输入字符 group: 一个分区中节点的集合，它也对应一个分区 groups: 当前分区集合 new: 当前分区中被拿出来的节点集合 first: 当前分区中第一个节点 next: 分区中不同于first的另一个节点，如果当前分区除了first对应节点外没有其他未访问过的节点，那么它取值nil go_first: first对应节点在接收c表示的输入后跳转的节点 go_next: next对应节点接收c表示输入后跳转的节点。

初始化： 先将所有非终结节点放入分区0，将所有终结节点放入分区1，于是groups中包含两个group对象

重复如下步骤，直到groups为空 for(从groups中取出一个group) { new = [] first = group中第一个节点 next = group中不同于first的节点，如果没有新节点那么设置为nil for next { for (当前输入字符c) { go_first = first 对应节点接收字符c后跳转的节点 go_next = next对应节点接收字符c后跳转的节点 if go_first 和 go_next不属于同一个分区，把next对应节点加入到集合new } next 指向当前集合中下一个节点 }

if new != nil { groups = append(groups, new } }

下面我们看看具体代码实现，在nfa_to_dfa.go中继续添加以下代码：

完成上面代码后，我们在main.go调用一下上面的实现：

上面代码运行后输出结果如下：

上面输出的跳转表画出来时可能跟我们上面不太一样，不一样的主要是节点的编号，但是节点的跳转结构跟我们在前面的分析完全相符，更详细的讲解和调试演示，请在B站搜索coding迪斯尼。