java - 实现非确定性有限自动机 (NFA)

Question

我正在尝试开发一个模拟程序，在 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

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

Answer 1

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

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

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

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

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