[java] How to implement a FSM - Finite State Machine in Java

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.

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

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

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

Here is a SUPER SIMPLE implementation/example of a FSM using just "if-else"s which avoids all of the above subclassing answers (taken from Using Finite State Machines for Pattern Matching in Java, where he is looking for a string which ends with "@" followed by numbers followed by "#"--see state graph here):

public static void main(String[] args) {
    String s = "A1@312#";
    String digits = "0123456789";
    int state = 0;
    for (int ind = 0; ind < s.length(); ind++) {
        if (state == 0) {
            if (s.charAt(ind) == '@')
                state = 1;
        } else {
            boolean isNumber = digits.indexOf(s.charAt(ind)) != -1;
            if (state == 1) {
                if (isNumber)
                    state = 2;
                else if (s.charAt(ind) == '@')
                    state = 1;
                else
                    state = 0;
            } else if (state == 2) {
                if (s.charAt(ind) == '#') {
                    state = 3;
                } else if (isNumber) {
                    state = 2;
                } else if (s.charAt(ind) == '@')
                    state = 1;
                else
                    state = 0;
            } else if (state == 3) {
                if (s.charAt(ind) == '@')
                    state = 1;
                else
                    state = 0;
            }
        }
    } //end for loop

    if (state == 3)
        System.out.println("It matches");
    else
        System.out.println("It does not match");
}

P.S: Does not answer your question directly, but shows you how to implement a FSM very easily in Java.

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

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