Design Considerations
Design Finite State Machine
Definitions
A person who never made a mistake never tried anything new.
— Albert Einstein
What is a finite state machine? A Finite State Machine or FSM is an abstract model of deterministic computation, which can be in only one finite state at a specific moment. Finite State Machines are used to model problems in different domains such as AI, games, or application flows. It describes how a program should behave by specifying states and routes between them.
Finite state machines are also called deterministic Finite Automaton.
Another open source implementation can be found under Easy States.
States
A state is a description of the status for a system that is waiting to execute a transition. A transition is a set of actions to be executed when an event is received. For example, when using an audio system to listen to the radio, receiving the next stimulus results in moving to the next station. When the system is in the "CD" state, the "next" stimulus results in moving to the next track. Identical stimuli trigger different actions depending on the current state.
It is also possible to associate actions with a state:
-
an entry action performed when entering the state, and
-
an exit action performed when exiting the state.
The set of possible states is defined as an enumeration type in our library.
States can contain substates. A state containing a set of substates is called a hierarchical state.
When you enter a hierarchical state, it is possible to define an initial state which is activated when a transition terminates on the border of the hierarchical state and no history is active.
A hierarchical state can have a history. When a transition terminates on the border of the hierarchical state with history, the latest active state is automatically activated. If no history is available, the default state is activated. If none is defined, an illegal state error occurs.
Events
An event is an external trigger processed in the finite state machine. The trigger can induce the firing of one transition.
The set of possible events is defined as an enumeration type in our library.
Transitions
A transition defines a potential change from one state to another one. A transition has a mandatory event triggering the firing of transition and an optional guard evaluation as a boolean condition.
A local transition is a transition starting and ending in the same state. When fired, the exit and entry actions of the state are not executed.
An external transition between two states or the same state. When fired, the exit and entry actions of the states are always executed.
Actions and Guards
An operation executed when the state machine processes an event. An action can be executed * when a transition is fired and the action is associated with the transition * when a state is entered through the firing of a transition * when a state is exited through the firing of a transition
An action has two parameters. The first is the context object owning the instance of the finite state machine. The second is the event being processed.
The order of the processing is the ordered list of actions associated with the exited states, the action on the transition, and the ordered list of actions associated with the entered states. The ordering is based on the traversal of the states seen from the transition being fired.
A guard evaluates a transition which could potentially be fired. A transition is only fired if the guard returns true and the transition event is the event being fired.
A guard has two parameters. The first is the context object owning the instance of the finite state machine. The second is the event being processed.
Finite State Machine Model
The event class triggering transitions in the finite state machine must be an enumeration type.
The state class defining the set of possible states in the finite state machine must be an enumeration type. the root state enclosing the whole machine is called per convention Root.
Finite State Machine Builder Model
The builder interfaces provide the implementation of the builder pattern to construct a finite state machine description using a fluent API.