问题标签 [dfa]

我意识到 DFA 是可数的，因为特定语言的 DFA 是所有 DFA 的子集。只是想知道如何证明接受特定语言的 DFA 的数量是无限的？

匹配可以重叠。

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

例如，要在字符串"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类。此外，如果有帮助，我还写了一系列关于我正在使用的构造算法的博客文章。

我对常规语言的概念有点困惑。由于 dfa 可以接受所有常规语言，并且 dfa 中总是有循环。所以看起来 dfa 可以接受无限数量的字符串。这是否意味着所有常规语言都是无限的？空集呢。是普通语言吗？

1. 表明语言不规则。L = {a^nb^m : n>m}

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

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

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

我正在尝试找到一种在 python 中最小化 DFA 的算法。我找到了一些例子，它们都有代码类。现在，我不知道如何转发放置在 .txt 文件中的 DFA 定义并将它们放入这些类中。.txt 格式如下：

1. line：由逗号分隔的状态集，按字典顺序排列
2. line：一组用逗号分隔的字母符号，按字典顺序排列
3. line：以逗号分隔的可接受状态集，按字典顺序排列
4. 行：第一个状态
5. 和所有其他行：格式为当前状态的传递函数，字母符号->下一个状态

定义示例：

类的例子

我加载 .txt 文件

给定{a^(n+m) | n>= 2m}，说明它是常规的、上下文无关的还是非上下文无关的，并使用 DFA、CFG、...

我的回答：它不是上下文无关的，因为没有办法表示 n>=2m。大于号太不明确了。

我想知道我的答案是否正确。

我想在基于 DFA 的正则表达式匹配器中实现“单词边界”匹配。有人能告诉我这是怎么做到的吗？

提供一些背景知识，我目前正在使用“dk.brics.automaton”库，但它不支持断言（例如\b，单词边界）。我需要使用基于 DFA 的引擎，因为我的主要目标实际上是确定正则表达式的等价性，而不是进行实际匹配。

此外，以下问题的答案似乎表明这是可能的： 基于 DFA 的正则表达式匹配 - 如何获取所有匹配项？ 通过说

“同样，我们通过向模拟器添加带有特殊指令的 epsilon 转换来管理这一点。如果断言通过，则状态指针继续，否则将被丢弃。”

然而，我不太明白这意味着什么。是否暗示它只能通过查看其端点的特殊类型的 epsilon 转换来完成，并且只有在其端点满足断言时才能被遍历，还是可以通过以某种方式配置的“正常”epsilon 转换来完成？如果我需要这些“特殊”类型的 epsilon 转换，那么如何确定这些（即转换为标准 DFA）？

非常感谢任何关于如何实际实现这一点的描述的指针。