问题标签 [dfa]

众所周知，DFA 可用于验证常规语言中的字符串。

示例 1. L=ac(b)*bcb|ad(b)*bb。DFA 可以验证字符串“acbbbcb”是否正确。

此外，有时，常规语言可以用 CFG 表示。

示例 2。

• S -> "a" A "b"
• A -> "c" B "c" | “D b
• B -> "b" B | “乙”

上述CFG生成的语言就是例1中的正则表达式。

这意味着，我们可以使用 DFA 来验证此 CFG 生成的（常规）字符串。但是，我们如何生成相应的解析树呢？

我目前正在尝试提出一种数据结构，以满足我想在 Haskell 中实现的两种自动机学习算法的需求：RPNI和EDSM。

直观地说，接近于 zippers 对树的东西将是完美的：这些算法是状态合并算法，它们保持对状态的某种关注（蓝色边缘），因此将受益于某种 zippers 快速到达有趣的点。但我有点迷失了，因为 DFA（确定性有限自动机）更像是一种图形结构而不是树状结构：转换可以让你回到结构中，这不太可能使拉链正常。

所以我的问题是：你将如何表示一个 DFA（或者至少是它的转换），以便你可以快速地操纵它？

我正在为自动机理论做作业，我必须确定一个词是否被确定性有限自动机的转移函数接受

我有这个输入文件：

输入以 4 个整数开头，第一个是自动机的状态数，接下来是自动机的转移数，第三个数字是初始状态，然后是最终状态数。然后是最终状态（在示例中，最终状态是 2 和 5）。

然后是 N 行（N 是转换的数量），每行有 2 个整数和一个字符 I、J 和 C，表示转换的状态，即转换从状态 i 到状态 J，字符 C。在这一行之后是一个整数 S，它将包含要测试的字符串的数量，然后是 S 行与相应的字符串。

这个程序的输出应该是：

它应该说明字符串是被接受还是被拒绝。到目前为止，我只使用输入对工作进行了编码。

我不知道如何最方便地表示 automaton。我应该简单地使用数组吗？我会对数组应用什么逻辑？在事先不知道自动机字母表的情况下，有什么办法可以做到吗？我需要一个数据结构来表示自动机吗？我对这个任务有点坚持，并且想要一些想法，一些伪代码或想法来完成它。代码是另一种语言吗？我不想要解决方案，因为我想做我的任务，但如果我可以使用一些帮助

我知道可以使用 if-else 方法和图形方法来实现 DFA，但是还有其他实现它们的方法吗？实际上，我正在为正则表达式创建一个 JavaCode 生成器，到目前为止，我已经完成了两种可能的方法（if-else 和图形方法），但我想提供更多可能的方法。我认为也许它可以使用一些数据结构作为转换的 Set 或 Map 来实现。

我尝试了几天来模拟一个非确定性有限自动机，使用我存储状态转换的地图，正如这篇文章中所指出的那样。

问题是它们缺少非确定性转换，即那些用相同符号引导我进入不同状态的转换。这是我的代码：

当我打印地图的全部内容时，这告诉我：

预期的输出是：

我究竟做错了什么。在另一个问题中，回答说模拟非确定性有限自动机转换的最佳方法是使用映射，但使用映射适合此类问题还是可以以任何方式解决？为什么这些值会丢失？

更改地图结构是否方便？IE：

我正在将一组给定的正则表达式转换为一个 NFA，但我遇到了一些问题。我应该如何转换诸如“ab.*c”之类的正则表达式（表示匹配一个'a'、一个'b'、任意数量的字符，然后是一个'c'）？

我的最终目标是将单个 NFA 转换为 DFA（为此我使用了子集构造算法）。

我想为 Unix 创建一个可以处理正则表达式的 C 程序，就像一个简单的 Perl 解释器。我必须亲自编写正则表达式引擎吗？

当我们从 nfa 转换为 dfa 时，可能会出现如下图所示的结果......我的问题是，是否有必要从状态 {4} 写入它会变为零状态？我的意思是不显示 {4} 的输入符号 1 与右下图相同？或没有？

我必须在 Java 中通过自动机实现以下操作：

• 级联
• 克莱恩之星
• 联盟
• 路口

如果自动机是 NFA，那么这些操作会更容易。我喜欢以下链接Modeling a Finite Deterministic Automaton via this data中给出的实现，但我认为这在建模 NFA 时不太合适，因为关键唯一性限制。你会给我推荐任何对 NFA 建模的解决方法吗？

我必须重构和维护一堆看起来很糟糕的 Java 类。许多具有以下实现模式

从这里我想生成一个图（使用 Graphviz 和dot）——有点像“静态调用图”，但不完全是。

除了使用 Perl 或 Python 自己解析 Java 代码之外，我在这里玩游戏如何自动执行此操作。

我真正想要的是拥有一个抽象语法树（AST）或类似的东西，我可以浏览并同时打印dot-code。

• 如何在这里生成可遍历的 AST？我想遍历将在 Java 中完成，但如果输出是任何文本表示形式，那就没问题（gprof想到这里）。
• 任何其他方法，不使用 AST？也许我只是个盲人，有一种更好、更简单的方法可以做到这一点。