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

User · Accepted Answer

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

User · Answer

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

User · Answer

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  Identify all possible states in your application  Identify all the events in your application  Identify all the conditions in your application  which may lead state transition  Occurrence of an event may cause transitions of state  Build a finite state machine by deciding a workflow of states  amp  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

User · Answer

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  lt  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

User · Answer

I design  amp  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 lt String  IState gt  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 lt String  IState gt  mMapping   new HashMap lt  gt         private String mStateName       public StateImpl String stateName            mStateName   stateName              Override     public Map lt String  IState gt  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 lt String  IState gt  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 lt IState gt  mAllStates   new ArrayList lt  gt         private HashMap lt String  ArrayList lt IState gt  gt  mMapForAllStates   new HashMap lt  gt          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 lt IState gt                  Override     public void setEndState IState endState            mEndState   endState          mAllStates add endState           mMapForAllStates put endState getStateDesc    new ArrayList lt IState gt                  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 lt IState gt              ArrayList lt IState gt  adjacentStateList   null          if  mMapForAllStates containsKey startStateDesc                 adjacentStateList   mMapForAllStates get startStateDesc               adjacentStateList add newState             else               mAllStates add startState               adjacentStateList   new ArrayList lt  gt                 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 lt String  IState gt  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

User · Answer

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 lt Symbol gt  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 lt Integer  Map lt Symbol  Integer gt  gt  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 lt Symbol  Integer gt  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

User · Answer

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

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

Examples related to java

Examples related to design-patterns

Examples related to state-machine

Examples related to fsm

Examples related to state-pattern