java - 如何用 Java 创建有限状态机

Question

如何编写一个程序来读取 FSM 的状态集。输入数据将来自格式为(状态输入下一个状态)的文本文件，最后一行是最终状态。例如:

    s0   a   s1
    s1   a   s2 
    s2   a   s2 
    s1 

程序输出将是:

a) FSM 生成的字符串列表。

b) 程序可以判断FSM是DFA还是NDFA并打印结果

Answer 1

我不会为您提供编码解决方案，而是提供一些思想方向。

首先，FSM 需要开始状态和结束状态，因此您会丢失重要信息。

如果您要生成字符串列表，那么您可能正在处理非常有限的 FSM 子集，这些子集接受有限数量的字符串。因此，尝试一切可能性是合理的；跟踪图表中的每条路径，并在达到结束状态时进行打印。

考虑一下 DFSM 与 NDFSM 的区别。如果有多种方法来处理某些输入，那么它是不确定的。因此，当您构建图表时，如果您有一个节点具有两次相同的到不同状态的转换，那么这是不确定的。由于任何非决定论都会使整个系统变得非决定论，决定论就是非决定论的完全缺失。

因此，您可能想要从实际创建表示开始。我想到了两种简单的方法。更直观的是，您可以创建一个图表。最简单的方法是创建一个节点类，然后为每个节点创建一个对象，其中包含成对的转换和目标。

我更喜欢表示 FSM 的一种方式是使用 HashMap /字典。使用节点和转换作为键，以目标作为值。这使得导航相当容易。

祝你好运!

编辑:在确定非确定性时，不要忘记考虑 epsilon 转换(就像我刚才所做的那样。:) )