c++ - 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 表示子集构造(也称为 powerset construction )。子集构建通过模拟 NFA 中每个等效状态集(由于 epsilon 转换)的所有转换来构建 DFA。

逆向 NFA 涉及以下步骤:

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

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

---

Brzozowski 算法示例

这是一个基于 Udacity quiz 最小化 DFA 的示例对于编译器类(class)(步骤与 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

第 3 步:反转(子集(反转(DFA))):

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

第 4 步: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

---

引用资料:

• Cooper 和 Torczon 的 Engineering a Compiler，第 2 版。第 49 页描述了子集构造，第 75 页描述了 Brzozowski 算法。

• Udacity's Compilers: Theory and Practice course , 第 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"];
}