问题标签 [nfa]

我有一个编译器问题。

确定是否 {(ab)^n | n >= 0} 是常规语言吗？

但我可以画出它的 NFA。但是如果我使用抽引引理，我会得到一个矛盾的答案。

谁能帮我 ？

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

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

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

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

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

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

我有一个关于将正则表达式转换为非确定性有限状态自动机的问题：

将 (a*|b*)* 转换为 NFA。我的尝试如下：

我完全偏离标准了吗？还是有些地方？

NB E => ε

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

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

(ab u aab u aba)*

我做到了，但我想要一些关于其正确性的反馈：

如果正确：我们可以进一步简化 (ab u aab u aba)* 吗？

如果没有：我错过了什么？

编辑：似乎我缺少从所有 3 个最终状态回到初始状态的电子转换，我需要一个初始和最终状态的新状态，它将在电子转换时进入旧的初始状态。（克莱恩星规则）。

PS我们也可以简化(a u b)*aabab和(a u b)*a(a u b)(a u b)(a u b)(a u b)。

我之所以问是因为如果没有办法简化/最小化，那将是一个非常长的 DFA ......

显而易见的选择是耗尽所有可能的输入。我想我做到了。但我不太确定它是否有效，并且我没有违反任何非确定性有限自动机的规则。

我的 NFA 由以下给出：(ab u aab u aba)*下面是我的图表。

我错过了什么吗？

我找到了这张图片，它代表 r* 表达式 NFA。我的问题是：不应该有一个箭头将第二个节点连接到第三个节点？这样，如果我有一个“rr”字符串，当第一个符号被读取时，我会进入第二个节点，但是从那里不能去任何地方，因为没有传出的箭头。 http://imageshack.us/f/641/screenshot20111021at114.png/

我面临的问题是，某个正则表达式实现是基于 DFA 还是 NFA。

我要解决这个问题的出发点是什么。也可以问：我在找什么？基本模式和/或特征是什么？一个好的和解释性的链接或一些比较（即使不直接专用于正则表达式）是非常好的。

我被分配了一个用 Java 模拟 NFA 的任务。现在，我必须为其模拟 NFA 的以下正则表达式是

我想我有太多的电子符号。我只是想知道下面的图片是否正确。