body continues in its state of rest, or of uniform
motion in a right line, unless it is compelled to
change that state by forces impressed upon it.”
— Sir Isaac Newton
Philosophiae Naturalis Principia Mathematica,
Laws of Motion, I , 1687
IN THIS CHAPTER,
YOU WILL LEARN:
The notation for
draw partitioned state-transition
How to build a
between STDs and other models.
In the previous chapters,
we have seen modeling tools that highlight the functions that
a system performs, as well as the stored data that
a system must remember. Now we look at a third
kind of modeling tool, the state-transition
known as STD), which highlights the time-dependent behavior
of a system.
Until recently, models of a system’s time-dependent
behavior were important only for a special category
of systems known as real-time systems. Examples of
these systems (which we discussed very briefly in
are process control, telephone switching systems,
high-speed data acquisition systems, and military
command and control systems. Some of these systems
are passive, in the sense that they do not seek to
control the surrounding environment, but rather to
react to it or capture data about it. Many high-speed
data acquisition systems fall into this category (e.g.,
a system capturing high-speed scientific data from
a satellite). Other real-time systems are more active,
in the sense that they seek to maintain control over
some aspect of the surrounding environment. Process
control systems and a variety of embedded systems
fall into this category.
As you might imagine, systems of this
kind deal with high-speed external sources of data, and
they must provide responses and output data quickly enough
An important part of specifying such systems is the description
of what happens when.
For business-oriented systems, this issue has generally
not been so important. Inputs may arrive in the system
from many different sources and at relatively high
speeds, but the inputs can usually be delayed if the
system is busy doing something else. A payroll system,
for example, does not have to worry about interrupts
and signals from external radar units. Typically,
the only timing issues that we see in such systems
are specifications of response time, which is included
in the user implementation model, which we discuss
in Chapter 21.
However, we are beginning to see some
large, complex business-oriented systems that do have aspects
of real-time behavior. If the system is dealing with inputs
as well as high-speed inputs from other computer systems
or satellite communication facilities, then it may have the
kind of time-dependent
classical real-time system has. Hence, though you may not
have to deal with such problems in every system you build,
be familiar with the
modeling tools for time-dependent behavior
13.1 STATE-TRANSITION DIAGRAM
A typical state-transition diagram is
shown in Figure 13.1(a) (though it is somewhat simpler
than the diagrams we will see later in this chapter).
the behavior of a
telephone answering machine.
The major components of the diagram are
states and arrows representing state changes. There
are a variety of alternative notations for state-transition
one is shown
in Figure 13.1(b). While it is equivalent in content
to Figure 13.1(a) it has the
disadvantage of looking too much like a dataflow diagram.
To avoid confusion, we will use the notation of Figure
A typical state-transition diagram
Figure 13.1(b): An
alternative state-transition diagram notation
Each rectangular box represents a state
that the system can be in. Webster’s New
World Dictionary defines
a “state” in
the following way:
A set of circumstances or
attributes characterizing a person or thing at a given time; way
or form of being; condition.
Thus, typical system states might be any
of the following:
Note that many of
these examples involve the system waiting for
something to occur and are not expressed in terms
of the computer doing something. This is because our state-transition
diagram is being used to develop an essential model of the
system , a model of
how the system would behave if we had perfect technology. One
aspect of perfect technology is that our computer operates infinitely
quickly, so any processing
or computation that the system has to do, or any action that it
has to take, will be done in zero time. Thus, any observable state
that the system is in can
only correspond to periods of time when (1) it is waiting for something
in the external environment to occur, or (2) it is waiting for
a current activity in
the environment (mixing, washing, filling, accelerating, etc.)
to change to some other activity.
This does not mean that our systems are
incapable of taking action or that we do not intend to show those
actions. It’s just that actions, which happen instantaneously in
our perfect technology model,
are not the same as states, which represent observable conditions
that the system can be in. Thus, a state represents some behavior
of the system that is
observable and that lasts for some finite period of time.
13.1.2 Changes of
A system that existed in only one state
would not be very interesting to study: it would be static.
Indeed, the information systems that we typically model may
have dozens of different states.
But how does a system change from one state to another? If the
system has orderly rules governing its behavior, then typically
only certain kinds of state
changes will be meaningful and valid.
We show the valid state changes on our
STD by connecting the relevant pairs of states with an arrow.
Thus, Figure 13.2 shows that the system can change from state
1 to state 2; it also shows that
when the system is in state 2, it can change to either state
3 or back to state 1. However, according to this STD, the system
cannot change from state
1directly to state 3. On the other hand, the diagram tells us
that the system can change directly from state 3 back to state
1. Note that state 2 has two
successor states. This is quite common in STDs; indeed, any
one state might lead to an arbitrary number of successor states.
Changes of state
While Figure 13.2 gives us some
interesting information about the time-dependent behavior
of a system, it does not tell us something that may turn
be very important: what the system’s initial and final states
are. Indeed, Figure 13.2 is a steady-state model of a
system that has been active forever and will continue
be active forever. Most systems do have a recognizable
initial state and a recognizable final state; this is
shown in Figure
Initial and final states
state is typically the one drawn at the
top of the diagram, though this is not
mandatory; what really identifies state 1 in
Figure 13.3 as the
initial state is the “naked” arrow
that is not connected to any other state. Similarly,
the final state is often the one drawn at the
bottom of the
diagram, but this is not
What really identifies state 5 as the final state
is the absence of an arrow leading out of state
5. In other
once you get to state 5,
Common sense tells us that a system can
have only one initial state; however, it can
have multiple final states; the various final states
that only one of them can
occur during any one execution of the system.
Figure 13.4 shows an example in which the possible
states are states
Multiple final states of a system
we are using STDs to build an essential model,
we also assume that state
changes occur instantaneously; that is, it requires
for the system to change
from one state into
another state. When the designers and programmers
begin to build an implementation model,
this will be a real issue: it typically does take
a few microseconds for a computer to switch
from one processing activity to another,
must ensure that it happens quickly enough
that the environment does not get out of
13.1.3 Conditions and
To make our state-transition diagram
complete, we need to add two more things:
the conditions that
cause a change of state, and the actions that
the system takes when it changes state.
As Figure 13.5 illustrates,
conditions and actions are shown next
to the arrow connecting two related
Showing conditions and actions
is some event in the external environment that
the system is
capable of detecting; it will typically be a signal,
or the arrival of a
packet of data. This will typically
cause the system to change from
state of waiting for X to a new state of waiting
But as part of the change of state,
the system will typically take
one or more actions:
it will produce an output,
display a message on the
user’s terminal, carry
out a calculation, and so on.
Thus, actions shown on the
STD are either responses sent back
results are remembered by the
system (typically in a data store shown
on the dataflow diagram) in
order to respond
to some future
In a complex system, there may be dozens
of distinct system states;
trying to show them all on a single diagram would
as we used leveling or partitioning
with dataflow diagrams, we
can use partitioning
with STDs. Figure 13.6(a) shows
an example of two levels
for a complex
Two levels of STD
Note that in this
case, any individual state of a higher-level
diagram can become the initial state
for a lower-level diagram
that further describes that higher-level
final state(s) in a lower-level
diagram correspond to the exit conditions
in the associated
higher-level state. In
the systems analyst may
need to show, explicitly, how a low-level
exits to an appropriate place
in the higher-level diagram.
An example of the need for a partitioned
diagram might be the automated teller machine
STD for this
application is shown
in Figure 13.6(b).
Figure 13.6(b): A
partitioned STD for an ATM machine
13.3 BUILDING THE STATE-TRANSITION
Now that we have seen the notation for
diagrams, we briefly discuss the steps in
can begin by identifying
as a separate
a sheet of paper.
between the boxes.
begin with the initial
way to the next state(s);
from the secondary
to the tertiary
and so on.
cases, by the
Have all states been
defined? Look at the system closely to see if there is any other observable
behavior or any other condition that the system could be in besides the ones
you have identified.
Can you reach all the
states? Have you defined any states that do not
have paths leading into them?
Can you exit from all
the states? As mentioned above, the system may
have one or more final states with multiple entrances
into them; but all other states must have a
In each state, does the
system respond properly to all possible conditions? This is the most
common error when building a state-transition diagram: the systems analyst
identifies the state changes when normal conditions occur, but fails to specify
the behavior of the system for unexpected conditions. Suppose the analyst has
modeled the behavior of a system as shown in Figure 13.7; she expects that the
user will press a function key on his terminal to cause a change from state 1 to
state 2 and a different function key to change from state 2 to state 3.
But what if the user presses the same function key twice in a row? Or some other
key? If the system behavior is not specified, there is a good chance that the
designers and programmers will not program for it either, and the system will
exhibit unpredictable behavior under a variety of
Figure 13.7: An
13.4 THE RELATIONSHIP TO OTHER
The state-transition diagram can be used
as a modeling tool by itself. However, it can be, and usually
should be, used in conjunction with those other tools.
In most cases, the state-transition
diagram represents a process specification for a control
bubble in a dataflow diagram. This is illustrated in Figure
that the conditions in the
STD correspond to incoming control flows on the
DFD, and the actions on the STD correspond to outgoing control
flows on the DFD. As a high-level modeling tool, the state-transition
diagram can even serve as a process
specification for the entire system. Thus, if we represent
system with a one-bubble dataflow
diagram , we can
use a state-transition diagram to show the sequence of
activities within the system.
Figure 13.8: Relationship
between DFD and STD
The state-transition diagram is a
powerful modeling tool for describing the required
behavior of real-time systems, as well as the human
portion of many
on-line systems. Though
it is not as widely known or used in the development
of business-oriented information systems, it is a tool
that you should become familiar
with, because, in the future, we can expect that more
and more systems, whether
business-oriented or scientific/engineering in nature,
will take on real-time overtones.
Second College Edition. New York: Simon & Schuster,
is a state-transition diagram? What is its purpose?
kind of system is most likely
to use an STD as a modeling tool?
STDs important tools for describing the requirements
of a typical
system? Why or why not?
STDs important tools for describing the design/implementation
a typical business-oriented
system? Why or
why not? If so, what kind
of business systems?
are the two major components of an STD?
an alternative notation for an STD, that is, one
different than the
diagrams shown in this
and throughout the book.
is the definition of a state?
three examples of a state.
is a change of state? How is it
shown on an STD?
is a successor state?
is the initial state of a system?
How many initial
states may there
be in a system?
is the final state of
How many final
may there be
in a system?
an STD? How
conditions can there
a “normal” mode,
as well as an alarm clock and a chronograph).
We will discuss the concept of an essential model
in more detail in Chapter
that to carry out an action the system may
require additional inputs from the external environment.
Thus, we can say that each condition corresponds
to an external event to which the system must respond, and
events will usually be recognized by the system when some incoming
dataflow arrives. However, it is not necessarily
true that every incoming dataflow to
the system is an event corresponding to a condition on the
Such a diagram is known as a context diagram. We
will discuss the context diagram in more detail