问题标签 [dfa]

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

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

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

这是DFA：

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

我需要为 CS 类使用 McNaughton-Yamada 算法构建 DFA。问题是算法是补充材料，我不清楚它到底是什么。它是一种在给定 RegEx 的情况下找到 DFA 的方法，还是找到 DFA 并最小化它？我似乎找不到有关该主题的任何信息。

我很困惑，因为我们在课堂上发现 DFA 后我的老师展示的最小化例程似乎与我们书中描述的“标记”最小化没有任何不同。

感谢您的回复，

弥敦道

我正在寻找一种将确定性有限自动机转换为下推自动机的算法。

任何帮助表示赞赏。

谢谢！

DFA 必须具有以下四个属性：

• DFA 有 N 个节点

• 每个节点有 2 个传出转换。

• 每个节点都可以从其他每个节点访问。

• DFA 是从所有可能性中以完全一致的随机性选择的

这是我到目前为止所拥有的：

1. 从 N 个节点的集合开始。
2. 选择一个尚未选择的节点。
3. 将其输出连接到其他 2 个随机选择的节点
4. 将一个转换标记为 1，将另一个转换标记为 0。
5. 转到 2，除非已选择所有节点。
6. 确定是否存在没有传入连接的节点。
7. 如果是这样，从具有超过 1 个传入连接的节点窃取传入连接。
8. 转到 6，除非没有没有传入连接的节点

但是，这是算法不正确的。考虑图中节点 1 有两个连接到节点 2（反之亦然），而节点 3 有两个连接到节点 4（反之亦然）。那是这样的：

1 <==> 2

3 <==> 4

其中，<==> 我的意思是双向两个传出连接（因此总共有 4 个连接）。这似乎形成了 2 个派系，这意味着并非每个州都可以从其他州到达。

有谁知道如何完成算法？或者，有人知道另一种算法吗？我似乎隐约记得可以使用二叉树来构造它，但我不确定。

我想知道如何在 C/C++/Java 中将 DFA 实现为链表。

当我从语法文件中生成带有 antlr 的词法分析器时，我注意到它会生成一系列十六进制格式的字符串。

DFA 使用这些字符串来预测我的下一个标记。

这些字符串是什么意思以及它们是如何生成的。

我引用的字符串出现在生成的词法分析器中，如下所示（a 并在构造函数中传递给 DFA）：

编辑：

我将开始回答自己的问题以帮助我们开始

acceptS[i] = 一个包含可能标记的标识符的数组（我不知道为什么它包含许多 -1 值）

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

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

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

我想编写一个将 nfa 转换为 dfa 的程序，用户绘制一个图形然后程序将其转换为 dfa 。我该怎么做？

我正在尝试实现 Brzozowski 的算法以最小化我的 DFA 以下是相同的算法。

其中r()是 NFA 的反转D()并将 NFA 转换为 DFA。

但我不明白r()在谷歌上搜索是什么意思也没有提供太多信息。

谁能解释一下什么是r()NFA。

任何其他可用的简单算法或 C++ 实现请告诉我链接。

与彼此相比，DFA 和 NFA 的相对优缺点是什么？

我知道 DFA 比 NFA 更容易实现，并且 NFA 到达接受状态的速度比 DFA 慢，但是还有其他明确的、众所周知的优点/缺点吗？