3

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

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

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

但我不明白r()在谷歌上搜索是什么意思也没有提供太多信息。

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

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

4

3 回答 3

2

这是来自 OpenFst 的实现。

本文中的图表（第 15 页）显示了应用反向操作的结果。

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

于 2011-05-05T08:49:08.923 回答
1

在 reverse.c 的代码（在此处找到，但现在已失效）中，您会找到一条注释/* Create reversed edges */。所以我会说这r()是反转所有边缘的方向（加上确保反转的自动机具有明确定义的起始状态）。

于 2011-05-05T07:16:43.967 回答
1

Brzozowski 算法

Brzozowski 的算法更清晰地写成：

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

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

逆转 NFA 涉及以下步骤：

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

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

Brzozowski 的算法示例

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

初始 DFA：

初始 DFA

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

第 1 步reverse(DFA)：：

反向（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

子集（反向（DFA））

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

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

反向（子集（反向（DFA）））

第 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

子集（反向（子集（反向（DFA））））

参考：

上图的 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"];
}
于 2020-04-25T19:40:35.350 回答