How to implement a FSM - Finite State Machine in J

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.

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

Answer 2

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).

Answer 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

Answer 4

I design & implemented a simple finite state machine example with java.

IFiniteStateMachine: The public interface to manage the finite state machine
such as add new states to the finite state machine or transit to next states by
specific actions.

interface IFiniteStateMachine {
    void setStartState(IState startState);

    void setEndState(IState endState);

    void addState(IState startState, IState newState, Action action);

    void removeState(String targetStateDesc);

    IState getCurrentState();

    IState getStartState();

    IState getEndState();

    void transit(Action action);
}

IState: The public interface to get state related info
such as state name and mappings to connected states.

interface IState {
    // Returns the mapping for which one action will lead to another state
    Map<String, IState> getAdjacentStates();

    String getStateDesc();

    void addTransit(Action action, IState nextState);

    void removeTransit(String targetStateDesc);
}

Action: the class which will cause the transition of states.

public class Action {
    private String mActionName;

    public Action(String actionName) {
        mActionName = actionName;
    }

    String getActionName() {
        return mActionName;
    }

    @Override
    public String toString() {
        return mActionName;
    }

}

StateImpl: the implementation of IState. I applied data structure such as HashMap to keep Action-State mappings.

public class StateImpl implements IState {
    private HashMap<String, IState> mMapping = new HashMap<>();
    private String mStateName;

    public StateImpl(String stateName) {
        mStateName = stateName;
    }

    @Override
    public Map<String, IState> getAdjacentStates() {
        return mMapping;
    }

    @Override
    public String getStateDesc() {
        return mStateName;
    }

    @Override
    public void addTransit(Action action, IState state) {
        mMapping.put(action.toString(), state);
    }

    @Override
    public void removeTransit(String targetStateDesc) {
        // get action which directs to target state
        String targetAction = null;
        for (Map.Entry<String, IState> entry : mMapping.entrySet()) {
            IState state = entry.getValue();
            if (state.getStateDesc().equals(targetStateDesc)) {
                targetAction = entry.getKey();
            }
        }
        mMapping.remove(targetAction);
    }

}

FiniteStateMachineImpl: Implementation of IFiniteStateMachine. I use ArrayList to keep all the states.

public class FiniteStateMachineImpl implements IFiniteStateMachine {
    private IState mStartState;
    private IState mEndState;
    private IState mCurrentState;
    private ArrayList<IState> mAllStates = new ArrayList<>();
    private HashMap<String, ArrayList<IState>> mMapForAllStates = new HashMap<>();

    public FiniteStateMachineImpl(){}
    @Override
    public void setStartState(IState startState) {
        mStartState = startState;
        mCurrentState = startState;
        mAllStates.add(startState);
        // todo: might have some value
        mMapForAllStates.put(startState.getStateDesc(), new ArrayList<IState>());
    }

    @Override
    public void setEndState(IState endState) {
        mEndState = endState;
        mAllStates.add(endState);
        mMapForAllStates.put(endState.getStateDesc(), new ArrayList<IState>());
    }

    @Override
    public void addState(IState startState, IState newState, Action action) {
        // validate startState, newState and action

        // update mapping in finite state machine
        mAllStates.add(newState);
        final String startStateDesc = startState.getStateDesc();
        final String newStateDesc = newState.getStateDesc();
        mMapForAllStates.put(newStateDesc, new ArrayList<IState>());
        ArrayList<IState> adjacentStateList = null;
        if (mMapForAllStates.containsKey(startStateDesc)) {
            adjacentStateList = mMapForAllStates.get(startStateDesc);
            adjacentStateList.add(newState);
        } else {
            mAllStates.add(startState);
            adjacentStateList = new ArrayList<>();
            adjacentStateList.add(newState);
        }
        mMapForAllStates.put(startStateDesc, adjacentStateList);

        // update mapping in startState
        for (IState state : mAllStates) {
            boolean isStartState = state.getStateDesc().equals(startState.getStateDesc());
            if (isStartState) {
                startState.addTransit(action, newState);
            }
        }
    }

    @Override
    public void removeState(String targetStateDesc) {
        // validate state
        if (!mMapForAllStates.containsKey(targetStateDesc)) {
            throw new RuntimeException("Don't have state: " + targetStateDesc);
        } else {
            // remove from mapping
            mMapForAllStates.remove(targetStateDesc);
        }

        // update all state
        IState targetState = null;
        for (IState state : mAllStates) {
            if (state.getStateDesc().equals(targetStateDesc)) {
                targetState = state;
            } else {
                state.removeTransit(targetStateDesc);
            }
        }

        mAllStates.remove(targetState);

    }

    @Override
    public IState getCurrentState() {
        return mCurrentState;
    }

    @Override
    public void transit(Action action) {
        if (mCurrentState == null) {
            throw new RuntimeException("Please setup start state");
        }
        Map<String, IState> localMapping = mCurrentState.getAdjacentStates();
        if (localMapping.containsKey(action.toString())) {
            mCurrentState = localMapping.get(action.toString());
        } else {
            throw new RuntimeException("No action start from current state");
        }
    }

    @Override
    public IState getStartState() {
        return mStartState;
    }

    @Override
    public IState getEndState() {
        return mEndState;
    }
}

example:

public class example {

    public static void main(String[] args) {
        System.out.println("Finite state machine!!!");
        IState startState = new StateImpl("start");
        IState endState = new StateImpl("end");
        IFiniteStateMachine fsm = new FiniteStateMachineImpl();
        fsm.setStartState(startState);
        fsm.setEndState(endState);
        IState middle1 = new StateImpl("middle1");
        middle1.addTransit(new Action("path1"), endState);
        fsm.addState(startState, middle1, new Action("path1"));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.transit(new Action(("path1")));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.addState(middle1, endState, new Action("path1-end"));
        fsm.transit(new Action(("path1-end")));
        System.out.println(fsm.getCurrentState().getStateDesc());
        fsm.addState(endState, middle1, new Action("path1-end"));
    }

}

Full example on Github

Answer 5

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

Answer 6

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