问题标签 [dfa]

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

我知道为正则表达式设计状态机生成器并非易事，但是简单的字符串呢（当我说一个简单的字符串时，我的意思是“abcd”之类的东西——没有任何正则表达式语法的东西）。我正在考虑使用状态机编写一个简单的字符串匹配器，但我希望在运行时生成状态机

状态机生成器的输入是要匹配的字符串，输出是状态机。我不是在寻找代码，而是在寻找一种方法/算法来做到这一点。

是的，我可以使用任何现成的库，但不，谢谢。

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

有没有人对构造两个给定 DFA 的并集的算法有简单的描述？例如，假设我们有两个超过 {0,1} 的 DFA，其中

我有一个结果转换表，将联合显示为：

我的讲义中有一个图形解决方案，但想看看其他人会如何描述它。由此，我可以看到，我们基本上使用它们的状态值“乘”这两个原始表以产生更大的转换表。因此可以从结果表中得出 DFA。这听起来是否正确，这是否适用于所有 DFA 案例，还是我遗漏了什么？

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

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

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

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

有限自治

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

在这里呈现形式：

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

我正在编写一个基于正则表达式的词法分析器生成器，该生成器基于 Dragon Book 中描述的正则表达式到 DFA 直接翻译算法。

它计算连接、交替和 kleene-star 节点的nullable、firstpos、lastpos和函数。followpos我想为+（一次或多次）和?（零次或一次）添加量词。

nullable, firstpos, 并且lastpos很容易计算，但我不确定followpos. 最好不要在解析阶段实现这些量词，而是在词法分析阶段重写它（我认为这只是 kleene-star 和交替的“句法糖”）？

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

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

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

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

谢谢。

用字母 { a }定义语言L如下

L = { 一个^nk | k > 0 ; n 是一个正整数常数 }

DFA 中识别L所需的状态数是多少？

在我看来它应该是 k+1 但我不确定。

这是一个家庭作业问题：

我知道 L 是非常规的，并且我知道 Kleene Star 是一个封闭的操作，所以我的假设是 L_4 是非常规的。

然而，我的教授提供了一个上面的例子L = {0^p | p is prime}，他说这是规则的，通过证明这L*等于L(000* + e)说每个都是彼此的子集（在这种情况下，e 表示空词）。

所以他的方法涉及形成一个正则表达式0^p，但是当我基本上已经有了一个正则表达式时，我该怎么做呢？