3.6 Finite State Machines

3.6.1 Description

Definition from Wikipedia:

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition, this is called a transition. A particular FSM is defined by a list of the possible states it can transition to from each state, and the triggering condition for each transition.

In ROOM each actor class can implement its behavior using a state machine. Events occurring at the end ports of an actor will be forwarded to and processed by the state machine. Events possibly trigger state transitions.

3.6.2 Motivation

For event driven systems a finite state machine is ideal for processing the stream of events. Typically during processing new events are produced which are sent to peer actors.

We distinguish flat and hierarchical state machines.

3.6.3 Notation

We distinguish flat finite state machines (with just one level of hierarchy) and hierarchical ones.

Flat Finite State Machine

The simpler flat finite state machines are composed of the elements shown in table 3.6.


Table 3.6: Flat finite state machine notation



Description

Graphical Notation

Textual Notation




State

PIC
State SomeState




InitialPoint

PIC

implicit




TransitionPoint

PIC
TransitionPoint tp




ChoicePoint

PIC
ChoicePoint cp




Initial Transition

PIC
Transition init: initial -> Initial { }




Triggered Transition

PIC
Transition tr0: initial -> DoingThis { 
 triggers { 
   <doThis: fct> 
 } 
}





Hierarchical Finite State Machine

The hierarchical finite state machine adds the notion of a sub state machine nested in a state. A few modeling elements listed in table 3.7 are added to the set listed above.


Table 3.7: Additional notation elements of hierarchical finite state machines



Description

Graphical Notation

Textual Notation




State with sub state machine

Parent State
PIC
Sub state machine

State Running { 
 subgraph { 
   Transition init: initial -> Process {} 
   State Process 
 } 
}




Entry Point

In sub state machine
PIC
EntryPoint reInit




Exit Point

PIC
ExitPoint tp0





3.6.4 Examples


PIC

Figure 3.1: Example of a flat finite state machine


PIC

Figure 3.2: Example of a hierarchical finite state machine – top level


PIC

Figure 3.3: Hierarchical finite state machine – sub state machine of Initializing


PIC

Figure 3.4: Hierarchical finite state machine – sub state machine of Running