Hopcroft算法划分解释

//基于等价类的思想
split(S){foreach(character c)if(c can split s)split s into T1, ..., Tk
}hopcroft()split all nodes into N, Awhile(set is still changes)split(s)

 根据状态是否为终结状态划分为终结状态A，和非终结状态N

对这两个大集合，分别进行hopcroft等价类判断，并进行划分

可以举例子来看一下

针对这个DFA图，首先将其切分为 N 和 A, N 是 q0, A 是 {q1, q2, q3}。

N无法再分，可以对A进行划分。

针对字符b，q1,q2,q3都将转到该集合

针对字符c，q1,q2,q3都将转到该集合，所以不需要对A进行划分。

因此最终得到的最小化DFA为

再举一个例子

N : {q0, q1, q2, q4}

A : {q3, q5}

针对N，字符e可以将q2，q4划分出去，q0和q1在接收e时仍在集合内部，但是q2和q4就会转移到q3，q5，因此得到{q0,q1}，{q2,q4}，{q3,q5}

针对{q0,q1}，字符e可以将q1划分出去，q0仍在集合内，q1会转移到{q2,q4}，因此可以划分为{q0},{q1}

针对{q2,q4},无法再分

针对{q3,q5}，无法再分