DFA 最小化 Brzozowski 算法

Question

我正在尝试实现 Brzozowski 算法来最小化我的 DFA 以下是相同的算法。

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

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

但我不明白r()的含义是什么，在google上搜索也没有提供太多信息。

谁能解释一下NFA的r()是什么。

任何其他可用的简单算法或 C++ 实现请让我知道链接。

Answer 1

Brzozowski 的算法

Brzozowski 的算法更清晰地写为：

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

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

反转 NFA 涉及以下步骤：

1. 反转 NFA 中所有过渡边的方向。
2. 创建一个新的起始状态，使 epsilon 转换到 NFA 中的所有接受状态。
3. 在 NFA 中将所有接受状态标记为不接受。
4. 使旧的起始状态成为新的接受状态。

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

---

Brzozowski 的算法示例

以下是基于针对编译器的 Udacity 测验 最小化 DFA 的示例当然（步骤与 NFA 作为初始输入相同）。

初始 DFA：

此 DFA 接受类似 {"", "a", "aa", "aaa", "aaabba", "ba", "bab", "ababa", "ababb"} 并拒绝像 {"b", "ab", "aab", "aabb", "bb", "bbb"} 这样的字符串。换句话说，它拒绝具有 "b" 的字符串，除非它们也具有 "ba" 子字符串。很明显，s1-s3 和 s2-s4 是多余的。

第 1 步：反向 (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

： net/bC85S.png" rel="nofollow noreferrer">

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

反转DFA。消除公共前缀后，另一遍可以消除公共后缀。

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

再次运行子集构造以最小化国家期货协会。

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

---

参考文献：

• Cooper 和 Torczon 的《工程编译器》，第二版。第 49 页描述了子集构造，第 75 页描述了 Brzozowski 算法。

• 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"];
}

Answer 2

这是 OpenFst 的实现。

在这篇论文中，有一个图表（第15页）显示了以下结果：应用相反的操作。

帮助理解 FSM 操作的一种更简单的方法是使用 OpenFst 等库来创建和操作机器，然后使用 Graphviz 将结果可视化。

Answer 3

在reverse.c的代码中（找到这里，但现在已不存在）您会发现注释/* Create reversed Edges */。所以我想说 r() 正在反转所有边的方向（另外还要确保反转的自动机具有明确定义的开始状态）。