-1

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

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

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

4

4 回答 4

4

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

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

于 2009-08-27T12:14:47.573 回答
1

你有编程问题,还是 Automata 有问题?

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

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

于 2009-08-27T12:11:05.653 回答
1

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

http://www.win.tue.nl/prose/pres/ploeger-19-10-06.pdf
http://www.cs.sun.ac.za/rw711/documentation/hopcroft2.pdf

于 2010-07-21T18:01:37.380 回答
0

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

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

于 2012-04-24T02:53:08.863 回答