问题标签 [nfa]

有什么证据可以证明这一点吗？我们怎么知道当前的 NFA 有最小的量呢？

我试图通过移植一个玩具 NFA 正则表达式匹配器来学习一些 clojure 。显然，我的主要问题是表示和操作图表。我找到了一个可行的解决方案，但我的实现（gensym基本上是用来模拟指针）让我嘴里有一种难吃的味道。

是否愿意提出改进建议，包括表示图形以及一般可读性和习语？（最初的命令式解决方案比我现在的更具可读性）。

干杯!

我知道将正则表达式转换为 NFA，有一个算法。

但我想知道是否有一种算法可以将 NFA 转换为正则表达式。如果有，它是什么？

如果没有，我也想知道是否所有 NFA 都可以转换为正则表达式。是否存在无法表示正则表达式的 NFA？

谢谢！:D

匹配可以重叠。

但是，如果从同一位置开始找到多个匹配项，则选择较短的一个。

例如，要在字符串"abcabdcd"中查找正则表达式部分"a.*d"，答案应该是 { "abcabd" , "abd" }。并且不应包含“abcabdcd”和“abdcd” 。

我希望在我的词法分析器中实现一个 DFA 最小化器，但我似乎无法生成一个看起来不像它已经是表达式的最小 DFA 的 DFA。

我正在从一个 NFA 构建 DFA，该 NFA 是使用来自后缀正则表达式的 thomson 构造构建的。这和龙书里描述的差不多。为了使词法分析器使用从开始状态的 epsilon 转换来组合几个 NFA。正是在这个组合的 NFA 上应用了 DFA 算法。

那么，是否有任何“已知”的正则表达式会生成一个 DFA，这将为死态消除和状态最小化提供一个很好的测试平台？

我当然可以破解一个奇怪的 DFA 并在其上应用算法，但它真的不是一个合适的测试用例吗？如果这样我构建 DFA 的方法不容易出现死状态，那么该信息将同样有价值，因为那时我可以完全跳过实现状态消除功能。

编辑：如果您需要实现细节以便准确回答，代码可在github上获得，特别是NFA.cs和DFA.cs类。此外，如果有帮助，我还写了一系列关于我正在使用的构造算法的博客文章。

给定两个不确定的有限自动机M1和M2，是否有一种有效的算法来确定M1接受的语言是否是M2接受的语言的超集？

我需要一个库，它将接受两个正则表达式并确定它们是否同构（即匹配完全相同的字符串集）例如 a|b 与 [ab] 同构

据我了解，正则表达式可以转换为 NFA，在某些情况下可以有效地转换为 DFA。然后可以将 DFA 转换为最小 DFA，如果我理解正确，它是唯一的，因此可以比较这些最小 DFA 是否相等。我意识到并非所有正则表达式 NFA 都可以有效地转换为 DFA（尤其是当它们是从不是真正“正则”的 Perl 正则表达式生成时），在这种情况下，理想情况下，库只会返回错误或其他指示转换是不可能。

我在网上看到了大量关于这样做的文章和学术论文（甚至是一些要求学生这样做的课程的编程作业），但我似乎找不到实现此功能的库。我更喜欢 Python 和/或 C/C++ 库，但任何语言的库都可以。有谁知道这样的图书馆吗？如果没有，是否有人知道我可以用作起点的接近的图书馆？

我如何证明这种语言是否正常？

L = {a ⁿ b ⁿ : n≥1} 并集 {a ⁿ b ⁿ⁺² : n≥1}

我正在学习一门计算课程，该课程还教授正则表达式。有一个很难回答的问题。

找到接受最多包含两对连续 0 的单词的语言的正则表达式。字母表由 0 和 1 组成。

首先，我制作了该语言的 NFA，但无法将其转换为 GNFA（后来被转换为正则表达式）。我怎样才能找到这个正则表达式？是否将其转换为 GNFA？

任何用于绘图机的轻量级 C 库？我进行了搜索，但是我发现的所有库都不是特定于任务的，它们很重。我需要一个用于绘图机的轻量级库。