如何在 Java 中实现 FSM - 有限状态机

Question

我有工作要做，我需要你的帮助。我们想实现一个 FSM - Finite State Machine 来识别字符序列（如：A、B、C、A、C），并判断它是否接受。

我们认为实现三个类： State 、 Event 和 Machine 。 state 类在 FSM 中表示一个节点，我们认为用 State design pattern 来实现它，每个节点都将从抽象类状态扩展并处理不同类型的事件并指示向新状态的转换。你认为这是个好主意吗？

第二件事，我们不知道如何保存所有的转换。我们再次考虑用某种 map 来实现它，它保持起点并获得带有下一个状态的某种向量，但我不确定这是一个好主意。

我很乐意得到一些关于如何实现它的想法，或者你可以给我一些起点。

我应该如何保存 FSM，这意味着我应该如何在程序开始时构建树？我用谷歌搜索并找到了很多例子，但没有什么对我有帮助。

非常感谢。

原文由 Ofir A. 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

状态机的核心是转换表，它将状态和符号（您称之为事件）带到新状态。这只是一个包含两个索引的状态数组。为了理智和类型安全，将状态和符号声明为枚举。我总是以某种方式（特定于语言）添加一个“长度”成员来检查数组边界。当我手动编码 FSM 时，我使用空白摆弄将代码格式化为行和列格式。状态机的其他元素是初始状态和接受状态集。接受状态集的最直接实现是由状态索引的布尔数组。然而，在 Java 中，枚举是类，您可以在声明中为每个枚举值指定一个“接受”参数，并在枚举的构造函数中对其进行初始化。

对于机器类型，您可以将其编写为泛型类。它需要两个类型参数，一个用于状态，一个用于符号，一个用于转换表的数组参数，一个用于初始状态的单个状态。唯一的其他细节（尽管很关键）是您必须调用 Enum.ordinal() 来获取适合索引转换数组的整数，因为您没有直接声明具有枚举索引的数组的语法（尽管应该是）。

为了抢占一个问题， EnumMap 不适用于转换表，因为所需的键是一对枚举值，而不是一个。

 enum State {
    Initial( false ),
    Final( true ),
    Error( false );
    static public final Integer length = 1 + Error.ordinal();

    final boolean accepting;

    State( boolean accepting ) {
        this.accepting = accepting;
    }
}

enum Symbol {
    A, B, C;
    static public final Integer length = 1 + C.ordinal();
}

State transition[][] = {
    //  A               B               C
    {
        State.Initial,  State.Final,    State.Error
    }, {
        State.Final,    State.Initial,  State.Error
    }
};

原文由 eh9 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

EasyFSM 是一个动态 Java 库，可用于实现 FSM。

您可以在以下位置找到相同的文档： Java 中的有限状态机

此外，您可以在以下位置下载该库： Java FSM 库：DynamicEasyFSM

原文由 user2968375 发布，翻译遵循 CC BY-SA 3.0 许可协议