finite-automata - NFA 到 DFA 算法

Question

我已经阅读了一个包含符号、状态和转换的文本文件，并将它们全部放在一个表格中。它看起来像这样：
符号 a、b
状态 q1、q2、q3、q4
开始状态 q4
最终状态 q2、q3

过渡状态：
q4, epsilon, q1
q1, a, q2
q3, a, q3
q3, b, q1

我已经阅读了有关如何将 NFA 转换为 DFA 的算法，但我并不真正了解该算法。我将如何创建转换方法以及我应该有什么状态类？

score 4 · Accepted Answer

我在这里有一个漂亮的链接： JFLAP

JFLAP 是一个 Java JAR，其中包含一些不错的可视化。您可以测试和转换 NFA/DFA，执行抽引引理并检查各种语法等等……您可以尝试一下！

score 1 · Accepted Answer

你有编程问题，还是 Automata 有问题？

因为编程这看起来很简单。是的，你有一个状态类，有 4 个可能的值 q1-a4。状态类有一个构造函数将其初始化为 q4。它有一个修改状态对象的 Accept(symbol) 函数，可能还有一个 IsEndState() 函数，它为状态 q2 和 q3 返回 true。

NFA/DFA 部分在 Accept() 方法的实现中发挥作用。现在可能会要求您提供一种程序解决方案来将基于 NFA 的 Accept() 实现转换为基于 DFA 的 Accept() 实现。

score 1 · Accepted Answer

这两个链接应该可以帮助您：

score 0 · Accepted Answer

如果您想自动执行此操作而无需下载 JFLAP 之类的东西，请尝试使用Online NFA 到 DFA 转换工具。

ProfBrown 在 YouTube 上的“将 NFA 转换为 DFA”视频探讨了如何严格执行此操作，尽管在 IMO 中必须手动编写表格是不切实际且不必要的乏味的。当您习惯于执行该过程时，您将能够将其用于小图。在大图的情况下，无论如何，你会使用一个工具来自动化它。

4 回答 4