实现非确定性有限自动机(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

我需要建议使用什么数据结构.我想过使用hashmaps和sets但是我不确定.

Answer 1

我认为你应该将你的自动机变成一个确定的自动机,然后做明显的事.

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

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

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

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