DFA最小化Brzozowski算法

Question

我正在尝试实现布鲁佐夫斯基算法来最小化我的DFA。以下是该算法的步骤：

DFA = d(r(d(r(NFA)))) 

其中 r() 是NFA的反转，D() 将NFA转换为DFA。

但我不明白 r() 的意思，在谷歌上搜索也没有给出太多信息。

有人能解释一下NFA中的 r() 吗？

如果有其他简单的算法或C++实现，请告诉我链接。

- Avinash

Answer 1

布鲁佐夫斯基算法

布鲁佐夫斯基算法通常被描述为：

minimized_DFA = subset(reverse(subset(reverse(NFA))))

其中subset表示子集构造（也称为powerset construction）。子集构造通过模拟NFA中每个等价状态集合的所有转换（由于epsilon转换）来构建DFA。

反转NFA需要以下步骤：

1. 反转NFA中所有转换边的方向。
2. 创建一个新的起始状态，该状态具有到NFA中所有接受状态的epsilon转换。
3. 将NFA中的所有接受状态标记为非接受状态。
4. 将旧的起始状态作为新的接受状态。

步骤2-4有效地交换了接受和起始状态的角色。

---

布鲁佐夫斯基算法举例

这是一个基于编译器课程Udacity测验的DFA最小化示例（使用NFA作为初始输入的步骤相同）。

初始DFA：

This DFA接受像{"", "a", "aa", "aaa", "aaabba", "ba", "bab", "ababa", "ababb"}这样的字符串，拒绝像{"b", "ab", "aab", "aabb", "bb", "bbb"}这样的字符串。换句话说，它拒绝没有"ba"子字符串的字符串，除非它们也有一个"b"。很明显，s1-s3和s2-s4是多余的。 第一步：reverse(DFA):

步骤2：subset(reverse(DFA))：

运行子集构造算法，构建一个DFA状态表格，表示从每个唯一的epsilon闭包可能的转换（^表示起始状态，$表示接受状态）：

A = e-closure({s5}) = {s0,s2,s4}
B = e-closure({s0,s1,s2,s3,s4}) = {s0,s1,s2,s3,s4}
C = e-closure({s2,s4}) = {s2,s4}
D = e-closure({s1,s2,s3,s4}) = {s1,s2,s3,s4}

     a   b
-----------
A^$  B   C
B$   B   B
C    D   C
D    D   B

步骤三：reverse(subset(reverse(DFA)))：

反转DFA。在消除公共前缀后，进行另一遍操作以消除公共后缀。

第四步: subset(reverse(subset(reverse(DFA)))):

再次运行子集构造来最小化NFA。

A = e-closure({E}) = {A,B}
B = e-closure({B,D}) = {B,D}
C = e-closure({A,B,C,D} = {A,B,C,D}

    a  b
--------
A^$ A  B
B   C  B
C$  C  C

---

参考文献:

• 《编译器工程》第2版，作者：Cooper and Torczon。子集构造算法在第49页描述，Brzozowski算法在第75页。

• Udacity的编译器理论和实践课程，第3课。

上述图表的Graphviz代码:

// initial DFA
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; s0 s2 s4;
    node [shape=circle];

    qi -> s0;
    s0 -> s0 [label="a"];
    s0 -> s1 [label="b"];
    s1 -> s2 [label="a"];
    s2 -> s2 [label="a"];
    s2 -> s4 [label="b"];
    s4 -> s4 [label="a,b"];
    s1 -> s3 [label="b"];
    s3 -> s3 [label="b"];
    s3 -> s2 [label="a"];
}

// reverse(DFA)
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; s0;
    node [shape=circle];

    qi -> s5;
    s0 -> s0 [label="a"];
    s1 -> s0 [label="b"];
    s2 -> s1 [label="a"];
    s2 -> s2 [label="a"];
    s4 -> s2 [label="b"];
    s4 -> s4 [label="a,b"];
    s3 -> s1 [label="b"];
    s3 -> s3 [label="b"];
    s2 -> s3 [label="a"];
    s5 -> s2 [label="e"];
    s5 -> s0 [label="e"];
    s5 -> s4 [label="e"];
}

// subset(reverse(DFA))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A B;
    node [shape=circle];

    qi -> A;
    A -> B [label="a"];
    A -> C [label="b"];
    B -> B [label="a,b"];
    D -> B [label="b"];
    C -> D [label="a"];
    C -> C [label="b"];
    D -> D [label="a"];
}

// reverse(subset(reverse(DFA)))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A;
    node [shape=circle];

    qi -> E;
    B -> A [label="a"];
    C -> A [label="b"];
    B -> B [label="a,b"];
    B -> D [label="b"];
    D -> C [label="a"];
    C -> C [label="b"];
    D -> D [label="a"];
    E -> A [label="e"];
    E -> B [label="e"];
}

// subset(reverse(subset(reverse(DFA))))
digraph G {
    rankdir=LR;
    size="8,5"
    
    node [shape=point]; qi;
    node [shape=doublecircle]; A C;
    node [shape=circle];

    qi -> A;
    A -> A [label="a"];
    A -> B [label="b"];
    B -> B [label="b"];
    B -> C [label="a"];
    C -> C [label="a,b"];
}

- ggorlen

Answer 2

这是来自OpenFst的实现。

在这篇论文中（此处），有一张图表（第15页）展示了应用反向操作后的结果。

理解有限状态机操作的更简单方法是使用类似OpenFst这样的库来创建和操作状态机，然后使用Graphviz可视化结果。

- Paul Dixon

Answer 3

在 reverse.c 的代码中（已经找不到了，但可以在 这里 找到），你会发现一个注释 /* Create reversed edges */。因此，我认为 r() 反转了所有边的方向（并确保反转的自动机具有明确定义的起始状态）。

- Andre Holzner

---

在提问之前，我确实查看了您的博客。请问您能帮我理解NFA的概念上的反转是什么意思吗？这是否意味着如果从状态S1到S2有一个转换，它会变成从S2到S1的转换，那么所有终止状态和非终止状态会发生什么变化呢？ - Avinash

这不是我的博客，但是我从代码中得到的印象与你所说的完全一致。当看到/* Create the new start state */后面的case语句时，我有一种印象，即该代码（reverse.c）创建了一个新的起始状态，并通过ε转换将其连接到原始NFA的所有终止状态。 - Andre Holzner

最终状态和非最终状态会发生什么情况。 - Avinash