如何在Java中实现FSM - 有限状态机 [英] How to implement a FSM - Finite State Machine in Java

问题描述

我有工作要做，我需要你的帮助。
要实现一个 FSM - 有限状态机，以识别字符序列（如：A，B，C，A，C），并告知是否

我们认为要实现三个类：状态，事件和机器。
状态类在 FSM 中显示一个节点，我们以为要实现它状态设计模式，每个节点将从抽象类状态扩展，每个类将处理不同类型的事件，并指示转换到新状态。对您的意见是个好主意吗？

第二件事，我们不知道如何保存所有的转换？再次，我们考虑用某种地图来实现它，这就是说明点，并获得某种向下的状态，但我不确定那是一个好的理念。

我很乐意获得一些如何实现它的想法，也许您可​​以给我一些起点。

如何保存FSM，这意味着如何在程序开始时构建树？
我google了，发现了很多例子，但没有什么可以帮助我。

非常感谢。

解决方案

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

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

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

 枚举状态{
初始（false），
 Final（true），
 Error（false）; 
 static public final整数长度= 1 + Error.ordinal（）; 
 
 final boolean accept; 
 
状态（布尔接受）{
 this.accepting = accept; 
} 
} 
 
枚举符号{
 A，B，C; 
 static public final整数长度= 1 + C.ordinal（）; 
} 
 
状态转换[] [] = {
 // ABC 
 {
 State.Initial，State.Final，State.Error 
}，{
 State.Final，State.Initial，State.Error 
} 
}; 
  

I have something to do for work and I need your help. We want to implement a FSM - Finite State Machine, to identify char sequence(like: A, B, C, A, C), and tell if it accepted.

We think to implement three classes: State, Event and Machine. The state class presents a node in the FSM, we thought to implement it with State design pattern, every node will extends from the abstract class state and every class would handle different types of events and indicate transitions to a new state. Is it good idea to your opinion?

Second thing, we don't know how to save all the transitions? Again we thought to implement it with some kind of map, that hold the stating point and gets some kind of vector with the next states, but I'm not sure thats a good idea.

I would be happy to get some ideas of how to implement it or maybe you can give me some starting points.

How should I save the FSM, meaning how should I build the tree at the beginning of the program? I googled it and found a lot of examples but nothing that helps me.

Thanks a lot.

解决方案

The heart of a state machine is the transition table, which takes a state and a symbol (what you're calling an event) to a new state. That's just a two-index array of states. For sanity and type safety, declare the states and symbols as enumerations. I always add a "length" member in some way (language-specific) for checking array bounds. When I've hand-coded FSM's, I format the code in row and column format with whitespace fiddling. The other elements of a state machine are the initial state and the set of accepting states. The most direct implementation of the set of accepting states is an array of booleans indexed by the states. In Java, however, enumerations are classes, and you can specify an argument "accepting" in the declaration for each enumerated value and initialize it in the constructor for the enumeration.

For the machine type, you can write it as a generic class. It would take two type arguments, one for the states and one for the symbols, an array argument for the transition table, a single state for the initial. The only other detail (though it's critical) is that you have to call Enum.ordinal() to get an integer suitable for indexing the transition array, since you there's no syntax for directly declaring an array with a enumeration index (though there ought to be).

To preempt one issue, EnumMap won't work for the transition table, because the key required is a pair of enumeration values, not a single one.

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
    }
};

这篇关于如何在Java中实现FSM - 有限状态机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！