6

我正在尝试开发一个在 Java 中执行非确定性有限自动机的模拟。第一个命令行参数是定义机器的文本文件。第二个参数是输入字符串。如果它接受字符串，它会打印到标准输出“accept”，然后是它可以结束的接受状态列表。如果它拒绝，它输出“reject”，然后是所有可能的结束状态的列表。

例如，文本：

state   1   start
state   2
state   7   accept
transition  1   0   1
transition  1   1   1
transition  1   0   2
transition  2   0   2
transition  2   0   1
transition  2   1   1
transition  2   0   7
transition  7   0   7
transition  7   1   7

看起来像：

看起来像：

输入字符串为 10 将输出

reject 1 2

输入字符串 000 将输出

accept 7

我需要关于使用什么数据结构的建议。我考虑过使用哈希图和集合，但我不确定。

4

2 回答 2

5

我认为你应该把你的自动机变成一个确定性的，然后做显而易见的事情。

在软件中实现有限状态机的常用方法有以下三种：

  • 将转换函数表示为表格（二维数组），并在读取每个字符时查找其中的下一个状态。
  • 对当前状态和输入字符使用嵌套switch语句来显式定义代码中的下一个状态。
  • 使用状态模式：将每个状态表示为一个类，并在给定输入字符的情况下使用返回下一个状态的方法。

由于您需要在运行时构建自动机，因此最后两个选项实际上并不适用，因此您应该使用查找表。如果你的字母表很小，你可以写下所有的转换。如果字母表很大，这可能会浪费很多空间，您可以考虑一下表压缩，它曾经是一个活跃的研究领域。

对于反对者：您不能编写“执行”非确定性自动机的确定性程序。但是，通过理论计算机科学的一个相当基本的定理，您可以通过完全自动化的过程将任何非确定性有限状态自动机转换为确定性自动机，即可以轻松在软件中实现的确定性算法。每个计算机科学专业的学生都应该使用铅笔和纸至少完成一次此过程。如果这样做，您将很快了解如何跟踪原始自动机的哪些状态进入确定性自动机的哪些状态。然后，简单地模拟后一种，看看它最终处于什么状态，并输出构成它的原始非确定性自动机的状态。

于 2014-09-13T23:30:11.853 回答
2

NFA 意味着您可以一次拥有一组状态。因此，要表示 NFA 的当前状态，请使用 Set 接口。

设置接口保证不会有任何重复的状态。这很重要，因为 NFA 一次有多个状态。如果您使用任何其他数据集，则此 gurrentee 不存在。在 NFA 的情况下，在每个转换中具有重复状态的机会是指数级的。但是状态集总是有限的。集合界面保证您当前的集合将充满重复项。

对于空间和性能，您可以使用 Enumset 作为 Enumset 使用位向量在内部存储状态。

算法：

初始化开始状态

从索引 0 开始从右到左处理字符串；

用于更新时使用状态转换的字符；

如果任何这种转换导致最终状态，这意味着字符串被接受。

于 2014-09-14T10:18:08.750 回答