SWD 392 - Software
Architecture and Design
SWD392
Finite State Machines
Here is whre your presentation begin
Introduction
Describes finite state machine modeling concepts. In particular, a
state-dependent control class needs to be modeled with a finite
state machine and depicted as a state chart.
Covers events, states, conditions, actions, entry and exit actions,
composite states, and sequential and orthogonal states
• Finite state machines are used for modeling the control and
sequencing view of a system or object.
• Notations used to define finite state machines are the state
transition diagram, statechart, and state transition table.
• In the UML notation, a state transition diagram is referred to
as a state machine diagram.
• The UML state machine diagram notation is based on Harel’s
statechart notation (Harel 1988; Harel and Politi 1998).
• This chapter starts by considering the characteristics of flat
statecharts and then describes hierarchical statecharts.
Table of contents
FINITE STATE MACHINES
01 02 EXAMPLES OF STATECHARTS
AND STATE TRANSITIONS
EVENTS AND GUARD
03 04 ACTIONS
CONDITIONS
GUIDELINES FOR
05 HIERARCHICAL STATECHARTS 06
DEVELOPING STATECHARTS
DEVELOPING STATECHARTS EXAMPLE OF DEVELOPING
07 08
FROM USE CASES A STATECHART FROM A USE CASE
01
FINITE STATE MACHINES
AND STATE TRANSITIONS
10.1 FINITE STATE MACHINES
AND STATE TRANSITIONS
• A finite state machine (also referred to as state machine) is a conceptual machine with a finite number of
states.
• A state transition is a change in state that is caused by an input event.
• Alternatively, the event might have no effect, in which case the finite state machine remains in the same
state. The next state depends on the current state, as well as on the input event.
• In an object-oriented model, the state-dependent view of a system is defined by means of one or more finite
state machines, in which each finite state machine is encapsulated inside its own object.
10.1.1 Events
• An event is an occurrence at a point
in time; it is also known as a discrete
event, discrete signal, or stimulus.
• The precedence of the two events is
reflected in the state that connects
them, as shown in Figure 10.1
10.1.2 States
• A state represents a recognizable situation that exists over an
interval of time.
• Alternatively, an event can have a null effect, in which case
the finite state machine remains in the same state.
• In theory, a state transition is meant to take zero time to
occur. In practice, the time for a state transition to occur is
negligible compared to the time spent in the state
02
EXAMPLES OF STATECHARTS
10.2 EXAMPLES OF STATECHARTS
The use of flat statecharts is illustrated by means of two examples, an ATM statechart and a Microwave
Oven statechart
10.2.1 Example of ATM Statechart
• Consider an example, shown in Figure 10.1, of a partial statechart for an automated teller
machine.
• The initial state of the ATM statechart is Idle.
• It is possible to have more than one transition out of a state, with each transition caused by a
different event.
• Figure 10.2 shows three possible state transitions out of the Validating PIN state. If the two PIN
numbers match, the ATM makes the Valid PIN
• In some cases, it is also possible for the same event to occur in different states and have
the same effect; an example is given in Figure 10.3.
• Next consider the case in which, after successful PIN validation, the customer decides to
withdraw cash from the ATM, as shown in Figure 10.4.
10.2.2 Example of Microwave Oven Statechart
• As a second example of a statechart, consider a simplified version of the
Microwave Oven Control statechart, which is shown in Figure 10.5.
• The statechart shows the different states for cooking food.
03
EVENTS AND GUARD
CONDITIONS
10.3 EVENTS AND GUARD CONDITIONS
• It is possible to make a state transition conditional through the use of a guard
condition.
• The notation used is Event [Condition].
• A condition is a Boolean expression with a value of True or False, which holds for some
time.
• The fact that an event has occurred can be stored as a condition that can be checked
later.
• Examples of guard conditions in Figure 10.6.
• -Zero Time and Time Remaining in the microwave statechart. The two transitions out of
the Door Open with Item state are Door Closed [Zero Time] and Door Closed [Time
Remaining].
04
ACTIONS
10.4 ACTIONS
• Associated with a state transition is an optional output action.
• An action is a computation that executes as a result of a state transition.
• The action executes instantaneously at the state transition; thus conceptually an
action is of zero duration.
• In practice, the duration of an action is very small compared to the duration of a
state.
10.4.1 Actions on State Transitions
• A transition action is an action that is a result of a transition from
one state to another – it could also happen if the state transitions to
itself.
• As an example of actions, consider the ATM statechart.
- This example is shown in Figure 10.7, which shows the partial
statechart for the ATM (originally shown in Figure 10.1) with the actions
added.
• An example of a statechart with alternative actions is shown in Figure 10.8.
• Another situation is that the same event can cause transitions out of several
states, with the same action in each case.
• An example of this is given in Figure 10.9.
10.4.2 Entry Actions
• An entry action is an instantaneous action that is performed on transition into
the state.
• Whereas transition actions (actions explicitly depicted on state transitions) can
always be used, entry actions should only be used in certain situations.
• The best time to use an entry action is when the following occur:
- There is more than one transition into a state.
- The same action needs to be performed on every transition into this state.
- The action is performed on entry into this state and not on exit from the
previous state.
• An example of an entry action is given in Figure 10.10.
10.4.3 Exit Actions
• An exit action is an instantaneous action that is performed on transition out of
the state.
• The best time to use an exit action is when the following occur:
- There is more than one transition out of a state.
- The same action needs to be performed on every transition out of the state.
- The action is performed on exit from this state and not on entry into the next
state.
• An example of an exit action is given in Figure 10.11.
05
HIERARCHICAL STATECHARTS
10.5 HIERARCHICAL STATECHARTS
• One of the potential problems of flat statecharts is the proliferation of states and transitions, which makes
the statechart very cluttered and difficult to read.
• A very important way of simplifying statecharts and increasing their modeling power is to introduce
composite states, which are also known as superstates, and the hierarchical decomposition of statecharts.
• The objective of hierarchical statecharts is to exploit the basic concepts and visual advantages of state
transition diagrams, while overcoming the disadvantages of overly complex and cluttered diagrams, through
hierarchical structuring.
10.5.1 Hierarchical State Decomposition
• Statecharts can often be significantly simplified by the hierarchical
decomposition of states.
• Composite state is decomposed into two or more interconnected sequential
substates.
• This kind of decomposition is referred to as sequential state decomposition.
• An example of hierarchical state decomposition is given in Figure 10.12a
10.5.2 Composite States
• Composite states can be depicted in two ways on statecharts, as described next.
• A composite state can be depicted with its internal substates, as shown for the
Processing Customer Input composite state in Figure 10.12a.
• Alternatively, a composite state can be depicted as a black box without
revealing its internal substates, as shown in Figure 10.12b
• Each transition into the composite state Processing Customer Input is, in fact, a
transition into one (and only one) of the substates on the lower-level
statechart.
10.5.3 Aggregation of State Transitions
• The hierarchical statechart notation also allows a transition out of every one of
the substates on a statechart to be aggregated into a transition out of the
composite state
• Careful use of this feature can significantly reduce the number of state
transitions on a statechart.
• Consider the Figure 10.9, in which aggregation of state transitions would be
useful.
• Customer to press the Cancel button on the ATM machine in any of the three
states Waiting for PIN, Validating PIN, and Waiting for Customer Choice.
10.5.4 Orthogonal Statecharts
• Another kind of hierarchical state decomposition is orthogonal state
decomposition, which is used to model different views of the same object’s state.
• With this approach, a high-level state on one statechart is decomposed into two
(or more) orthogonal statecharts.
• . Although orthogonal statecharts can be used to depict concurrent activity
within the object containing the statechart, it is better to use this kind of
decomposition to show different parts of the same object that are not
concurrent.
• The use of orthogonal statecharts to depict conditions can be seen in the ATM
example.
• This case is illustrated in Figure 10.13
9.1.2 Sequence Diagrams
• The interaction among objects can also be shown on a sequence diagram.
• A sequence diagram shows the objects participating in the interaction and the
sequence in which messages are sent.
• Sequence diagrams can also depict loops and iterations.
• Sequence diagrams and communication diagrams depict similar (although not
necessarily identical) information, but in different ways.
• In the following example, however, the messages on the sequence diagram are
numbered to show their correspondence to the communication diagram.
• An example of a sequence diagram for the View Alarms use case is shown in
Figure 9.3. This sequence diagram conveys the same information as the
communication diagram shown in Figure 9.2.
06
GUIDELINES FOR
DEVELOPING STATECHARTS
10.6 GUIDELINES FOR
DEVELOPING STATECHARTS
• The following guidelines apply to developing either flat or hierarchical statecharts, unless otherwise
explicitly stated:
- A state name must reflect an identifiable situation or an interval of time when something is happening in the
system.
- On a given statechart, each state must have a unique name.
- It must be possible to exit from every state.
- On a sequential statechart, the statechart is in only one state at a time.
- Do not confuse events and actions.
- An event happens at a moment in time.
- An action is a command – for example, Dispense Cash, Start Cooking, Eject.
- An action executes instantaneously.
- A condition is a Boolean value.
- Actions and conditions are optional.
07
DEVELOPING STATECHARTS
FROM USE CASES
10.7 DEVELOPING STATECHARTS
FROM USE CASES
• To develop a statechart from a use case, start with a typical scenario given by the use case – that is, one
particular path through the use case.
• Usually, an input event from the external environment causes a transition to a new state, which is given a
name corresponding to what happens in that state.
• Initially, a flat statechart is developed that follows the event sequence given in the main scenario.
• In fact, the states represent consequences of actions taken by the actor, either directly or indirectly.
• The actions resulting from each alternative state transition also need to be considered.
• The partial statecharts will need to be integrated to form a complete statechart.
• To integrate two partial statecharts, it is neces- sary to find one or more common states.
• A common state might be the last state of one statechart and the first state of the next statechart.
• The integration approach is to integrate the partial statecharts at the common state, in effect superimposing
the common state of the second statechart on top of the same state on the first statechart.
• There are actually two main approaches to developing hierarchical statecharts.
- top-down approach
- first develop
08
EXAMPLE OF DEVELOPING
A STATECHART FROM A USE CASE
10.8 EXAMPLE OF DEVELOPING
A STATECHART FROM A USE CASE
Consider the ATM Control statechart from the Banking System case study.
10.8.1 Develop Statechart for Each Use Case
• In this example, we will consider the use cases for Validate PIN and Withdraw Cash.
• For each use case, a statechart is constructed as illustrated in Figures 10.14 and 10.15.
10.8.2 Consider Alternative Sequences
• After the first version of the statechart is completed, further refinements can
be made
• To complete the statechart, it is necessary to consider the effect of each
alternative sequence described in the Alternatives section of the use cases.
• Figure 10.16 shows the Withdraw Funds statechart with the alternative
sequences added to the main sequence.
10.8.3 Develop Integrated Statechart
• The integrated statechart consists of the integration of the use case–based
statecharts, after consideration of alternatives.
• This statechart would represent the main sequence through each use case
together with the alternatives.
• Figure 10.17 shows the integrated statechart from the Validate PIN and
Withdraw Cash statecharts, with main and alternatives sequences.
10.8.4 Develop Hierarchical Statechart
• It is usually easier to initially develop a flat statechart.
After enhancing the flat statechart by considering alternative events.
- Look for ways to simplify the statechart by developing a hierarchical
statechart.
- In particular, look for situations in which the aggregation of state transitions
simplifies the statechart.
• The hierarchical statechart for ATM Control is shown in Figures 10.18 through
10.21.
Thanks!