Hopcroft算法DFA最小化Python实现

DFA最小化原理

所谓自动机的化简问题即是对任何一个确定有限自动机DFA M，构造另一个确定有限自动机DFA M’，有L（M）＝L（M’），并且M’的状态个数不多于M的状态个数，而且可以肯定地说，能够找到一个状态个数为最小的M’。

下面首先来介绍一些相关的基本概念。

 设S_i是自动机M的一个状态，从S_i出发能导出的所有符号串集合记为L（S_i）。

 设有两个状态S_i和S_j，若有L（S_i）＝L（S_j），则称S_i和S_j是等价状态。

上图所示的自动机中L（B）＝L（C）＝{1}，所有状态B和状态C是等价状态。

又例如终态导出的符号串集合中必然包含空串ε，而非终止状态导出的符号串集合中不可能包含空串ε，所以终态和非终止状态是不等价的。

对于等价的概念，我们还可以从另一个角度来给出定义。

给定一个DFA M，如果从某个状态P开始，以字符串w作为输入，DFA M将结束于终态，而从另一状态Q开始，以字符串w作为输入，DFA M将结束于非终止状态，则称字符串w把状态P和状态Q区分开来。

把不可区分开来的两个状态称为等价状态。

设S_i是自动机M的一个状态，如果从开始状态不可能达到该状态S_i，则称S_i为无用状态。

设S_i是自动机M的一个状态，如果对任何输入符号a都转到其本身，而不可能达到终止状态，则称S_i为死状态。

化简DFA关键在于把它的状态集分成一些两两互不相交的子集，使得任何两个不相交的子集间的状态都是可区分的，而同一个子集中的任何两个状态都是等价的，这样可以以一个状态作为代表而删去其他等价的状态，然后将无关状态删去，也就获得了状态数最小的DFA。

下面具体介绍DFA的化简算法：

• 首先将DFA M的状态划分出终止状态集K₁和非终止状态集K₂。

K＝K₁∪K₂

由上述定义知，K₁和K₂是不等价的。

• 对各状态集每次按下面的方法进一步划分，直到不再产生新的划分。

设第i次划分已将状态集划分为k组，即：

K＝K₁⁽ⁱ⁾∪K₂⁽ⁱ⁾∪…∪K_k⁽ⁱ⁾

对于状态集K_j⁽ⁱ⁾（j=1,2,…,k）中的各个状态逐个检查，设有两个状态K_j’、 K_j’’∈K_j⁽ⁱ⁾，且对于输入符号a，有：

F（K_j'，a）＝K_m

F（K_j''，a）＝K_n

如果K_m和K_n属于同一个状态集合，则将K_j’和K_j’’放到同一集合中，否则将K_j’和K_j’’分为两个集合。

• 重复第（2）步，直到每一个集合不能再划分为止，此时每个状态集合中的状态均是等价的。
• 合并等价状态，即在等价状态集中取任意一个状态作为代表，删去其他一切等价状态。
• 若有无关状态，则将其删去。

根据以上方法就将确定有限自动机进行了简化，而且简化后的自动机是原自动机的状态最少的自动机。

Hopcroft算法原理

算法抽象：

• 1: Q/θ ← {F, Q − F}
• 2: while (∃U, V ∈ Q/θ, a ∈ Σ) s.t. Equation 1 holds do
• 3: Q/θ ← (Q/θ − {U}) ∪ {U ∩ δ^-1(V, a), U − U ∩ δ^-1(V, a)}
• 4: end while

算法细化：

• 1:W ← {F, Q − F}    # 有些版本上只是 W ← {F }
• 2: P ← {F, Q − F}
• 3: while W is not empty do
• 4:     select and remove S from W
• 5:     for all a ∈ Σ do
• 6:         la ← δ^-1(S, a)
• 7:         for all R in P such that R ∩ la ≠ ∅ and R ∉ la do
• 8:             partition R into R1 and R2: R1 ← R ∩ la and R2 ← R − R1
• 9:             replace R in P with R1 and R2
• 10:           if R ∈ W then
• 11:               replace R in W with R1 and R2
• 12:           else
• 13:                 if |R1| ≤ |R2| then
• 14:                     add R1 to W
• 15:                 else
• 16:                     add R2 to W
• 17:                 end if
• 18:             end if
• 19:         end for
• 20:    end for
• 21: end while

流程图

Python代码

测试

测试数据：

起始节点、边、终止节点的表示

共有14个边，7个节点

图形显示:

刚开始的子集为[{C,D,E,F},{S，A，B}]

实验结束后的结果：

最简化的DFA为：

C为终止节点，S为起始节点

难点与解决的方法

• 在DFA最小化的过程中受限要去除无用状态，再使用子集分割算法处理。根据资料查找到一个快速的DFA最小化算法，叫做Hopcroft算法，通过该算法，能够处理不同大小字母表的DFA。
• 在进行子集分割算法后，要合并等价的节点并且重命名使用graphviz输出，在这一步，合并并重命名节点需要注意所有重复节点的入度和出度均要考虑，只有这样才能避免新的最小化的DFA的边不遗漏。