DFA Minimization Brzozowski算法

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

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

其中r()是NFA和D()的反转转换NFA到DFA。

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

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

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

2011-05-05 Avinash

在reverse.c的代码中（找到~~here~~，但现在已不存在），您会发现评论/* Create reversed edges */。所以我认为r()是反转所有边缘的方向（加上确保反转自动机具有明确的启动状态）。

2011-05-05 07:16:43

在提出问题之前，我曾看过您的博客。你能帮我理解NFA的概念是什么意思吗？这是否意味着如果从状态S1转换到S2，它变成S2到S1以及所有最终状态和非最终状态发生了什么。 – Avinash 2011-05-05 07:21:25

这不是我的博客，但是，我从代码中得到的印象正是你所说的。在'/ *创建新的开始状态* /'之后查看'case'语句时，我感觉代码（reverse.c）创建了一个新的开始状态并将其连接到原始NFA的所有结束状态通过一个epsilon过渡。 – 2011-05-05 07:29:16

最终状态和非最终状态会发生什么。 – Avinash 2011-05-05 07:41:02

This是OpenFst的实现。

在this纸是显示应用反转操作的结果的图（第15页）。

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

2011-05-05 08:49:08

回答