问题标签 [nfa]

正如我在这篇文章中解释的那样，我正在做一个模拟非确定性有限自动机的任务。我从文件中读取了这个输入tarea4.in：

输入的第一行是一个整数 T，表示要评估程序的案例数。每个测试用例以 4 个整数开头，第一个是自动机的状态数，接下来是自动机的转换数，第三个数字是初始状态，然后是最终状态数。然后是最终状态（在示例中，最终状态是 2 和 5）。然后是 F 行，每行都有一个整数 E，表示 E 是一个最终状态。

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

预期的输出是：

产生我的代码的输出：

这是我的代码：

我的问题是：为什么我得到不正确的输出？我认为这是因为测试用例中定义的自动机的不确定性，但是我如何正确评估字符串？如何evaluate_string以某种方式将调用的函数更改为检查可以使自动机通过非确定性评估字符串的不同路径？

我已经坚持了好几天了，老实说，我有点绝望。

几天来，我试图做一个程序来模拟一个不确定的有限自动机（NFA），更具体地说，一个字符串识别器。在几次失败后，感谢用户Konrad Rudolph，我可以根据这个伪代码实现一个解决方案：

好吧，在 NFA 中，您有一组当前状态，并且在每个步骤中，您都会遍历所有当前状态，并且为每个状态选择所有有效转换。这些组合集形成了您的新状态集。

最后，检查当前状态和接受状态的交集是否为非空。

在伪代码中，如下所示：

这可以逐行翻译成 C++ 代码。他建议让这个简单，使用std::set<int> for the current and next sets

这是我在 C++ 中的实现：

我有这个输入：

预期的输出是：

但是，我的代码作为输出生成：

而对于测试用例的最后一个字符串，程序什么也不做，只是不停止运行。我的问题是为什么我的程序会因这个特定的输入而崩溃。我在JFlap中设计了相同的自动机 NFA并识别了最后一个输入

呸呸呸呸

.

我在执行代码时犯了什么错误？

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

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

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

哪一种是显示 RE 联合 0+1 的正确方法？我看到了这两种方式，但我认为两者都是正确的。如果两者都是正确的，为什么要把事情复杂化？

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

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

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

我有一个关于 DFA 最小化的问题。因此，我使用了众所周知的技术将正则表达式转换为 NFA，然后使用 goto / 闭包算法从中构造 DFA。现在的问题是如何最小化它？我在这里看过有关它的演讲：http ://www.youtube.com/watch?v=T9Z66NF5YRk，但我仍然无法理解这一点。什么是 DFA 最小化？这只是合并相同的状态（在相同字符上进入相同状态的状态）还是不同的东西？

所以，我从以下语法开始：

并最终得到以下 DFA（表示为 JSON）：

那么如何最小化它呢？

更新：

好的，这是我的算法。给定以下 DFA：

这就是我为最小化它所做的事情：

1. 对于每个状态（在我的示例中编号为 0、1、2、3、4），获取标识此类状态的唯一哈希（例如，对于 state0，这将是：from=97,to=97,shift=1，对于 state1，此将是：from=97,to=97,shift=3&from=98,to=98,shift=2 等等...)

2. 比较获得的哈希值，如果我们找到两个相同的哈希值，则将其合并。在我的例子中，state2 hash 为：from=98&shift=4&to=98，state4 hash 为：from=98&shift=4&to=98，它们是相同的，所以我们可以将它们合并到新的 state5 中，之后 DFA 将看起来像这样：

   }

3. 继续这个，直到我们没有任何变化，所以下一步（合并状态 1 和 3）会将 DFA 转换为以下形式：

   }

4. 没有更多相同的状态，这意味着我们完成了。

第二次更新：

好的，给定以下正则表达式： 'a' ('ce')* ('d' | 'xa' | 'AFe')+ | 'b' ('ce')* ('d' | 'xa' | 'AFe')+ 'ce'+ 我有以下 DFA (START -> start state, ["accept"] -> so to说转换到接受状态）：

故事是一样的，我如何最小化它？如果我遵循经典的 Hopcroft 算法来构建所有这些表，确定不可区分的状态，将它们合并在一起等等，那么我将获得包含 15 个状态的 DFA（使用此工具：http ://regexvisualizer.apphb.com/使用这个正则表达式 a(ce) (d|xa|AFe)+|b(ce) (d|xa|AFe)+ce+ 来检查）。以下是使用 Hopcroft 算法缩小后 DFA 的样子：

我想出的算法，在“重新思考” Hopcroft 的算法之后，构建的 DFA 比您在上面看到的要小（对不起图像质量，我不得不一步一步地重新绘制它以了解为什么它更小）：

这就是它的工作原理，关于“状态等价”的决定是基于给定状态（例如“START”）的哈希函数的结果，如果我们从该状态开始，可以构建可以从 DFA 构造的短字符串. 给定上面的 DFA 和 START 状态，我们可以构造以下字符串：98->120, 98->100, 98->65, 98->99, 97->120, 97->100, 97->65 , 97->99 所以让它成为 START 状态的哈希函数的结果。如果我们为 DFA 中的每个状态运行此函数，我们将看到对于某些状态，此函数为我们提供相同的结果（“1.2”、“6.7”、“2.3”和“10”、“13”和“15” ，“16”和“11”，“8”，“26”，“23”和“12”，“9”，“4”，

我看到我在某个地方错了，但不明白我的算法产生的最小化 DFA 有什么问题？

我被要求构建一个 DFA A 和 NFA B，使得 L(D) = L(N) 具有某些特定条件。我不是在寻求解决方案或答案；我只是想确保我有正确的方法来解决这个问题。

首先，我对“构建”这个词有点困惑。他们只是想画一个自动机吗？那会被认为是“建成”吗？

我正在考虑绘制适合该条件的 NFA B。然后使用绘图，我将构造一个等价的 DFA A。在某处有一个定理说等价的自动机具有相同的语言。所以我不需要做任何进一步的事情来显示 L(A) = L(B) 对吗？

谢谢！

从正则表达式创建 NFA 时，我遇到了“描述每个步骤”的问题。问题如下：

将以下正则表达式转换为非确定性有限状态自动机 (NFA)，清楚地描述您使用的算法的步骤：(b|a)*b(a|b)

我已经制作了一个简单的三态机器，但它很大程度上来自直觉。这是我的讲师写的过去考试中的一个问题，他还写了对汤普森算法的以下解释：http ://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

谁能弄清楚如何“清楚地描述每个步骤”？它似乎只是一组基本规则，而不是一个需要遵循的步骤的算法。

也许有一种算法我已经在某处掩盖了，但到目前为止，我只是用有根据的猜测创建了它们。

我正在经历过去的考试，并且不断遇到我在教科书或谷歌上找不到答案的问题，因此非常感谢任何帮助。

我目前遇到的问题如下：

给定正则表达式 (a|bb)*，推导出将其转换为相应 NFA 和 DFA 的时间成本估计值。您的答案应该参考正则表达式的大小。

另一年的一个类似问题是：

鉴于以上示例，您知道原始正则表达式的大小 |r| 和输入字符串 |x| 的大小，解释如何计算构建和运行 NFA 与构建和运行等效 DFA 的时间成本。

(a|bb)* 得到的 NFA 有 9 个状态，而 DFA 有 4 个状态。即使知道这一点，我也不知道如何解决这个问题。