MENU

词法分析——DFA 的最小化:Hopcroft 算法

October 11, 2018 • Read: 361 • 编译原理

通过前面对于词法自动生成部分的学习,我们已经掌握了如何从源码生成到 DFA

那么为什么要对 DFA 进行最小化处理呢?

下面给出一个例子:

如下是我们之前写出的 a(b|c)* 的 NFA:

它可以对应转换成如下的 DFA:

在上面的 DFA 中非接受状态和接受状态是不能够合并的,因为如果合并,就会接受一个$\epsilon$串,这是明显不正确的。但是如果同样是接受状态或者同样是非接受状态的话就有可能。例如可以将$q_2$和$q_3$进行合并,得到一个新的接受状态$q_4$。得到新的 DFA,如下:

之后,我们还可以再对$q_1$和$q_5$进行融合得到$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$。

再给一个例子


N : {$q_0,q_1,q_2,q_4$}
A : {$q_3,q_5$}

在 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$}。

最后编辑于: October 18, 2018
Archives Tip
QR Code for this page
Tipping QR Code