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

Question

我有工作要做，需要你的帮助。我们想要实现一个FSM - 有限状态机，来识别字符序列(比如:A、B、C、A、C)，并判断它是否被接受。

我们想实现三个类:State、Event和Machine。state类在FSM中呈现了一个节点，我们想用State设计模式来实现它，每个节点都会从抽象类状态扩展而来每个类都会处理不同类型的事件并指示到新状态的转换。您认为这是个好主意吗？

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

我很乐意了解如何实现它，或者您可以给我一些起点。

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

非常感谢。

Answer 1

状态机的核心是转换表，它将一个状态和一个符号(您称之为事件)带到一个新状态。这只是一个包含两个索引的状态数组。为了理智和类型安全，将状态和符号声明为枚举。我总是以某种方式(特定于语言)添加一个“长度”成员来检查数组边界。当我手动编码 FSM 时，我使用空白摆弄将代码格式化为行和列格式。状态机的其他元素是初始状态和接受状态集。接受状态集的最直接实现是由状态索引的 boolean 数组。然而，在 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
    }
};