How to implement a FSM - Finite State Machine in Java

Question

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 extend 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 in 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 starting 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.

Solution 1

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

Solution 2

EasyFSM is a dynamic Java Library which can be used to implement an FSM.

You can find documentation for the same at : Finite State Machine in Java

Also, you can download the library at : Java FSM Library : DynamicEasyFSM

Solution 3

You can implement Finite State Machine in two different ways.

Option 1:

Finite State machine with a pre-defined workflow : Recommended if you know all states in advance and state machine is almost fixed without any changes in future

1. Identify all possible states in your application

2. Identify all the events in your application

3. Identify all the conditions in your application, which may lead state transition

4. Occurrence of an event may cause transitions of state

5. Build a finite state machine by deciding a workflow of states & transitions.

   e.g If an event 1 occurs at State 1, the state will be updated and machine state may still be in state 1.

   If an event 2 occurs at State 1, on some condition evaluation, the system will move from State 1 to State 2

This design is based on State and Context patterns.

Have a look at Finite State Machine prototype classes.

Option 2:

Behavioural trees: Recommended if there are frequent changes to state machine workflow. You can dynamically add new behaviour without breaking the tree.

The base Task class provides a interface for all these tasks, the leaf tasks are the ones just mentioned, and the parent tasks are the interior nodes that decide which task to execute next.

The Tasks have only the logic they need to actually do what is required of them, all the decision logic of whether a task has started or not, if it needs to update, if it has finished with success, etc. is grouped in the TaskController class, and added by composition.

The decorators are tasks that “decorate” another class by wrapping over it and giving it additional logic.

Finally, the Blackboard class is a class owned by the parent AI that every task has a reference to. It works as a knowledge database for all the leaf tasks

Have a look at this article by Jaime Barrachina Verdia for more details

Solution 4

Hmm, I would suggest that you use Flyweight to implement the states. Purpose: Avoid the memory overhead of a large number of small objects. State machines can get very, very big.

http://en.wikipedia.org/wiki/Flyweight_pattern

I'm not sure that I see the need to use design pattern State to implement the nodes. The nodes in a state machine are stateless. They just match the current input symbol to the available transitions from the current state. That is, unless I have entirely forgotten how they work (which is a definite possiblilty).

If I were coding it, I would do something like this:

interface FsmNode {
  public boolean canConsume(Symbol sym);
  public FsmNode consume(Symbol sym);
  // Other methods here to identify the state we are in
}

  List<Symbol> input = getSymbols();
  FsmNode current = getStartState();
  for (final Symbol sym : input) {
    if (!current.canConsume(sym)) {
      throw new RuntimeException("FSM node " + current + " can't consume symbol " + sym);
    }
    current = current.consume(sym);
  }
  System.out.println("FSM consumed all input, end state is " + current);

What would Flyweight do in this case? Well, underneath the FsmNode there would probably be something like this:

Map<Integer, Map<Symbol, Integer>> fsm; // A state is an Integer, the transitions are from symbol to state number
FsmState makeState(int stateNum) {
  return new FsmState() {
    public FsmState consume(final Symbol sym) {
      final Map<Symbol, Integer> transitions = fsm.get(stateNum);
      if (transisions == null) {
        throw new RuntimeException("Illegal state number " + stateNum);
      }
      final Integer nextState = transitions.get(sym);  // May be null if no transition
      return nextState;
    }
    public boolean canConsume(final Symbol sym) {
      return consume(sym) != null;
    }
  }
}

This creates the State objects on a need-to-use basis, It allows you to use a much more efficient underlying mechanism to store the actual state machine. The one I use here (Map(Integer, Map(Symbol, Integer))) is not particulary efficient.

Note that the Wikipedia page focuses on the cases where many somewhat similar objects share the similar data, as is the case in the String implementation in Java. In my opinion, Flyweight is a tad more general, and covers any on-demand creation of objects with a short life span (use more CPU to save on a more efficient underlying data structure).

Solution 5

Consider the easy, lightweight Java library EasyFlow. From their docs:

With EasyFlow you can:

• implement complex logic but keep your code simple and clean
• handle asynchronous calls with ease and elegance
• avoid concurrency by using event-driven programming approach
• avoid StackOverflow error by avoiding recursion
• simplify design, programming and testing of complex java applications

View more solutions