问题标签 [nfa]

有谁知道 C# 中有任何好的 NFA 和 DFA 实现，可能还实现了两者之间的转换？我希望能够构建一个 NFA，然后将其自动转换为 DFA，而不必编写我自己的代码，这将花费很长时间。有这个Python 代码，也许我可以使用 IronPython 并与 C# 集成，但是 Python 很慢。

我正在寻找一个可以将非确定性有限自动机转换为确定性有限自动机的 Java 库。有没有？

有人能比我简洁地向 SO 社区描述 NFA 到 DFA 的转换算法吗？（最好是 500 字或更少。）我看到的图表和讲座只会混淆我以为我曾经知道的东西。我最有信心从状态图中生成初始 NFA 转换表，但在那之后，我失去了 epsilons 和子集中的 DFA。

1) 在转换（delta）表中，哪一列代表新的 DFA 状态？它是生成状态的第一列吗？

2) 在我下面示例的第 {2,3} 行第 0 列中，就 NFA 的状态图而言，{2,3} 是什么意思？（对不起，我必须在图片中思考。）我认为这将是 DFA 中的“输入 0 环回”？

3) 关于从表到 DFA 或识别结果 DFA 的接受状态的任何简单“经验法则”？

有限自治

编辑：这是上面的点格式表格，欢呼Regexident。

在这里呈现形式：

注意：该表缺少有关州接受度的任何信息，因此图表也是如此。

在我的词法分析器生成器中，我使用 McNaughton 和 Yamada 算法构建 NFA，它的属性之一是从 I 转换为 J，在 J 位置用 char 标记。

因此，NFA 的每个节点都可以简单地表示为下一个可能状态的列表。

哪种数据结构最适合存储此类数据？它必须为所有可能的状态提供快速查找并使用更少的空间，但插入时间并不那么重要。

我正在寻找关于哪个更好用以及在什么情况下在编译器中使用 nfa 或 dfa 的讨论。模拟 nfa 与 dfa 的时间复杂度权衡是什么，在编译器的什么情况下哪个更适合？

我开始寻找一个体面的正则表达式引擎。它把我带到了这个页面 正则表达式库的基准。我决定使用RE2，因为它似乎是这个列表中最好的 FSA 引擎。

我的最终应用程序将使用 C# 中的 WPF 构建。正则表达式库将更多地用于批处理模式。然而，大多数其他业务逻辑将用 C# 编写，因此我计划通过 C# 使用 RE2 库。

如果有人做过类似的事情或只是通过 C# 使用 RE2 并有一些建议或指示，请告诉我。

谢谢。

有人能告诉我换能器与 NFA 有何不同吗？

NFA 优于 DFA：表示使用更少的内存。

NFA 与 NFA 相比的缺点： 较慢地得出答案。

还有其他优点或缺点吗？

我得到了一个正则表达式，我想将其转换为 NFA，然后是 DFA。这是正则表达式：

a ( b | c )* a | aac* b

然后我使用汤姆森算法将其转换为 NFA：

这是DFA：

有人可以快速看一下让我知道我是错还是对？

有人可以帮我解决这个问题吗？

描述一种将 NFA 转换为语言是 L(A) 补码的 DFA 的算法。补码应针对 A 的字母表。给出一个非正式的论据来说明您的构造为何有效。您无需提供正式证明。

任何形式的指导表示赞赏...