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

Question

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

    s0   a   s1
    s1   a   s2 
    s2   a   s2 
    s1

程序输出将是：

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

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

score 2 · Accepted Answer

我不会给你一个编码的解决方案，而是一些思路。

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

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

想想 DFSM 与 NDFSM 的区别。如果有多种方法可以使用某些输入，则它是不确定的。因此，当您构建图表时，如果您有一个节点具有两个相同的转换到不同状态的节点，那是不确定的。由于任何非确定性都会使整个系统成为非确定性的，因此确定性就是完全没有非确定性。

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

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

祝你好运！

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

1 回答 1