approximation to the true square root. You may want to use Matlab for this.
Lee & Varaiya, Signals and Systems
91
EXERCISES
92
Lee & Varaiya, Signals and Systems
3
State Machines
Contents
3.1
Structure of state machines . . . . . . . . . . . . . . . . . . . . . .
3.1.1
Updates . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2
Stuttering . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2
Finite state machines
. . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1
State transition diagrams . . . . . . . . . . . . . . . . . . . .
3.2.2
Update table
. . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3
Nondeterministic state machines . . . . . . . . . . . . . . . . . . . 107
3.3.1
State transition diagram
. . . . . . . . . . . . . . . . . . . . 107
3.3.2
Sets and functions model . . . . . . . . . . . . . . . . . . . . 110
3.4
Simulation relations . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.4.1
Relating behaviors . . . . . . . . . . . . . . . . . . . . . . . 119
3.5
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Systems are functions that transform signals. The domain and the range of these functions
are both signal spaces, which significantly complicates specification of the functions. A
broad class of systems can be characterized using the concept of state and the idea that
a system evolves through a sequence of changes in state, or state transitions. Such
characterizations are called state-space models.
A state-space model describes a system procedurally, giving a sequence of step-by-step
operations for the evolution of a system. It shows how the input signal drives changes in
93
3.1. STRUCTURE OF STATE MACHINES
state, and how the output signal is produced. It is thus an imperative description. Imple-
menting a system described by a state-space model in software or hardware is straight-
forward. The hardware or software simply needs to sequentially carry out the steps given
by the model. Conversely, given a piece of software or hardware, it is often useful to
describe it using a state-space model, which yields better to analysis than more informal
descriptions.
In this chapter, we introduce state-space models by discussing systems with a finite (and
relatively small) number of states. Such systems typically operate on event streams, of-
ten implementing control logic. For example, the decision logic of modem negotiation
described in Chapter 1 can be modeled using a finite state model. Such a model is much
more precise than the English-language descriptions that are commonly used for such
systems.
3.1
Structure of state machines
A description of a system as a function involves three entities: the set of input signals, the
set of output signals, and the function itself,
F : InputSignals → OutputSignals.
For a state machine, the input and output signals have the form
EventStream : N0 → Symbols,
where N0 = {0, 1, 2, · · · }, and Symbols is an arbitrary set. The domain of these signals
represents ordering but not necessarily time (neither discrete nor continuous time). The
ordering of the domain means that we can say that one event occurs before or after another
event. But we cannot say how much time elapsed between these events. In Chapter 5 we
will study how state-space models can be used with functions of time.
A state machine constructs the output signal one symbol at a time by observing the input
signal one symbol at a time. Specifically, a state machine StateMachine is a 5-tuple,
StateMachine = (States, Inputs, Outputs, update, initialState)
(3.1)
where States, Inputs, Outputs are sets, update is a function, and initialState ∈ States. The
meaning of these names is:
94
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
States is the state space,
Inputs is the input alphabet,
Outputs is the output alphabet,
initialState ∈ States is the initial state, and
update : States × Inputs → States × Outputs is the update function.
This five-tuple is called the sets and functions model of a state machine.
Inputs and Outputs are the sets of possible input and output symbols. The set of input
signals consists of all infinite sequences of input symbols,
InputSignals = [N0 → Inputs].
The set of output signals consists of all infinite sequences of output symbols,
OutputSignals = [N0 → Outputs].
Let x ∈ InputSignals be an input signal. A particular symbol in the signal can be written
x(n) for any n ∈ N0. We write the entire input signal as a sequence
(x(0), x(1), · · · , x(n), · · · ).
This sequence defines the function x in terms of symbols x(n) ∈ Inputs, which represent
particular input symbols.
We reiterate that the index n in x(n) does not refer to time, but rather to the step number.
This is an ordering constraint only: step n occurs after step n − 1 and before step n + 1.
The state machine evolves (i.e. moves from one state to the next) in steps.1
3.1.1
Updates
The interpretation of update is this. If s(n) ∈ States is the current state at step n, and
x(n) ∈ Inputs is the current input symbol, then the current output symbol and the next
state are given by
(s(n + 1), y(n)) = update(s(n), x(n)).
1Of course the steps could last a fixed duration of time, in which case there would be a simple relation-
ship between step number and time. The relationship may be a mixed one, where some input symbols are
separated by a fixed amount of time and some are not.
Lee & Varaiya, Signals and Systems
95
3.1. STRUCTURE OF STATE MACHINES
Thus the update function makes it possible for the state machine to construct the output
signal step by step by observing the input signal step by step.
The state machine StateMachine of (3.1) defines a function
F : InputSignals → OutputSignals
(3.2)
such that for any input signal x ∈ InputSignals the corresponding output signal is y = F(x).
However, it does much more than just define this function. It also gives us a procedure for
evaluating this function on a particular input signal. The state response (s(0), s(1), · · · )
and output signal y are constructed as follows:
s(0)
=
initialState,
(3.3)
∀n ≥ 0, (s(n + 1),y(n)) = update(s(n),x(n)),
(3.4)
Observe that if the initial state is changed, the function F will change, so the initial state
is an essential part of the definition of a state machine.
Each evaluation of (3.4) is called a reaction because it defines how the state machine
reacts to a particular input symbol. Note that exactly one output symbol is produced for
each input symbol. Thus, it is not necessary to have access to the entire input sequence
to start producing output symbols. This feature proves extremely useful in practice, since
it is usually impractical to have access to the entire input sequence (it is infinite in size!).
The procedure summarized by (3.3)–(3.4) is causal, in that the next state s(n + 1) and
current output symbol y(n) depend only on the initial state s(0) and current and past input
symbols x(0), x(1), · · · , x(n).
It is sometimes convenient to decompose update into two functions:
nextState : States × Inputs → States is the next state function,
output : States × Inputs → Outputs is the output function.
The interpretation is this. If s(n) is the current state, and x(n) is the current input symbol
at step n, the next state is
s(n + 1) = nextState(s(n), x(n)),
and the current output symbol is
y(n) = output(s(n), x(n)).
Evidently, for all s(n) ∈ States and x(n) ∈ Inputs,
(s(n + 1), y(n)) = update(s(n), x(n)) = (nextState(s(n), x(n)), output(s(n), x(n)).
96
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
3.1.2
Stuttering
A state machine produces exactly one output symbol for each input symbol. For each
input symbol, it may also change state (of course, it could also remain in the same state
by changing back to the same state). This means that with no input symbol, there is
neither an output symbol nor a change of state.
Later, when we compose simpler state machines to construct more complicated ones, it
will prove convenient to be explicit in the model about the fact that no input triggers no
output and no state change. We do that by insisting that the input and output symbol sets
include a stuttering symbol, typically denoted absent. That is,
absent ∈ Inputs, and absent ∈ Outputs.
Moreover, we require that for any s ∈ States,
update(s, absent) = (s, absent).
(3.5)
This is called a stuttering reaction because no progress is made. An absent input symbol
triggers an absent output symbol and no state change. Now any number of absent sym-
bols may be inserted into the input sequence, anywhere, without changing the non-absent
output symbols. Stuttering reactions will prove essential for hybrid systems models, con-
sidered in Chapter 6.
Example 3.1:
Consider a 60-minute parking meter.
There are three (non-
stuttering) input symbols: in5 and in25 which represent feeding the meter 5 and
25 cents respectively, and tick which represents the passage of one minute. The
meter displays the time in minutes remaining before the meter expires. When in5
occurs, this time is incremented by 5, and when in25 occurs it is incremented by
25, up to a maximum of 60 minutes. When tick occurs, the time is decremented
by 1, down to a minimum of 0. When the remaining time is 0, the display reads
expired.
We can construct a finite state machine model for this parking meter. The set of
states is
States = {0, 1, 2, ..., 60}.
The input and output alphabets are
Inputs = {in5, in25, tick, absent},
Lee & Varaiya, Signals and Systems
97
3.2. FINITE STATE MACHINES
Outputs = {expired, 1, 2, ..., 60, absent}.
The initial state is
initialState = 0.
The update function
update : States × Inputs → States × Outputs
is given by, ∀ s(n) ∈ States, x(n) ∈ Inputs,
(0, expired)
if x(n) = tick ∧ (s(n) = 0 ∨ s(n) = 1)
(s(n) − 1, s(n) − 1)
if x(n) = tick ∧ s(n) > 1
(min(s(n) + 5, 60), min(s(n) + 5, 60))
update(s(n), x(n)) =
if x(n) = in5
(min(s(n) + 25, 60), min(s(n) + 25, 60))
if x(n) = in25
(s(n), absent)
if x(n) = absent
where min is a function that returns the minimum of its arguments.
If the input sequence is (in25, tick20, in5, tick10, · · · ), for example, then the output
sequence is
(expired, 25, 24, ..., 6, 5, 10, 9, 8, · · · , 2, 1, expired, · · · ).
Here, we are using the common notation tick10 to mean a sequence of 10 consecu-
tive ticks.
3.2
Finite state machines
Often, States is a finite set. In this case, the state machine is called a finite state machine,
abbreviated FSM. FSMs yield to powerful analytical techniques because, in principle, it
is possible to explore all possible sequences of states. The parking meter above is a finite
98
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
state machine. The remainder of this chapter and the next chapter will focus on finite state
machines. We will return to infinite state systems in Chapter 5.
When the number of states is small, and the input and output alphabets are finite (and
small), we can describe the state machine using a very readable and intuitive diagram
called a state transition diagram.
Example 3.2: A verbal description of an automatic telephone answering service
or voice-mail service might go like this.
When a call arrives, the phone rings. If the phone is not picked up, then
on the third ring, the service answers. It plays a pre-recorded greeting
requesting that the caller leave a message (“Hello, sorry I can’t answer
your call right now ... Please leave a message after the beep”), then
records the caller’s message, and then automatically hangs up. If the
phone is answered before the third ring, the service does nothing.
Figure 3.1 shows a state transition diagram for the state machine model of this
answering service.
You can probably read the diagram in Figure 3.1 without any further explanation. It is
sufficiently intuitive. Nonetheless, we will explain it precisely.
3.2.1
State transition diagrams
Figure 3.1 consists of bubbles linked by arcs. (The arcs are also called arrows.) In this
bubbles-and-arcs syntax each bubble represents one state of the answering service, and
each arc represents a transition from one state to another. The bubbles and arcs are
annotated, i.e. they are labeled with some text. The execution of the state machine consists
of a sequence reactions, where each reaction involves a transition from one state to another
(or back to the same state) along one of the arcs. The tables at the bottom of the figure are
not part of the state transition diagram, but they improve our understanding of the diagram
by giving the meanings of the names of the states, input symbols, and output symbols.
The notation for state transition diagrams is summarized in Figure 3.2. Each bubble is
labeled with the name of the state it represents. The state names can be anything, but they
Lee & Varaiya, Signals and Systems
99
3.2. FINITE STATE MACHINES
must be distinct. The state machine of Figure 3.1 has five states. The state names define
the state space,
States = {idle, count1, count2, play greeting, recording}.
Each arc is labeled by a guard and (optionally) an output. If an output symbol is given,
it is separated from the guard by a forward slash, as in the example {ring}/answer going
from state count2 to play greeting. A guard specifies which input symbols might trigger
the associated transition. It is a subset of the Inputs, the input alphabet, which for the
answering service is
Inputs = {ring, offhook, end greeting, end message, absent}.
In Figure 3.1, some guards are labeled “else.” This special notation designates an arc that
is taken when there is no match on any other guard emerging from a given state. The arc
with the guard else is called the else arc. Thus, else is the set of all input symbols not
included in any other guard emerging from the state. More precisely, for a given state,
else is the complement with respect to Inputs of the union of the guards on emerging arcs.
For example in Figure 3.1, for state recording,
else = {ring, end greeting}.
For the example in Figure 3.2, else is defined by
else = {i ∈ Inputs | i /
∈ (guard1 ∪ guard2)}.
If no else arc is specified, and the set else is not empty, then the else arc is implicitly a self
loop, as shown by the dashed arc in figure 3.2. A self loop is an arc that transitions back
to the same state. When the else arc is a self loop, then the stuttering symbol may be a
member of the set else.
Initially, the system of Figure 3.1 is in the idle state. The initial state is indicated by
the bold arc on the left that leads into the state idle. Each time an input symbol arrives,
the state machine reacts. It checks the guards on arcs going out of the current state and
determines which of them contains the input symbol. It then takes that transition.
Two problems might occur.
• The input symbol may not be contained in the guard of any outgoing arc. In our
state machine models, for every state, there is at least one outgoing transition that
100
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
matches the input symbol (because of the else arc). This property is called recep-
tiveness; it means that the machine can always react to an input symbol. That is,
there is always a transition out of the current state that is enabled by the current
input symbol. (The transition may lead back to current state if it is a self loop.) Our
state machines are said to be receptive.
• More than one guard going out from the current state may contain the input symbol.
A state machine that has such a structure is said to be nondeterministic. The
machine is free to choose any arc whose guard contains the input symbol, so more
than one behavior is possible for the machine. Nondeterministic state machines
will be discussed further below. Until then, we assume that the guards are always
defined to give deterministic state machines. Specifically, the guards on outgoing
arcs from any state are mutually exclusive. In other words, the intersection of any
two guards on outgoing arcs of a state is empty, as indicated in Figure 3.2. Of
course, by the definition of the else set, for any guard that is not else, it is true that
guard ∩ else = /0.
A sequence of input symbols thus triggers a sequence of state transitions. The resulting
sequence of states is called the state response.
Example 3.3: In Figure 3.1, if the input sequence is
(ring, ring, offhook, · · · )
then the state response is
(idle, count1, count2, idle, · · · ).
The ellipsis (“· · · ”) are there because the answering service generally responds to
an infinite input sequence, and we are showing only the beginning of that response.
This behavior can be compactly represented by a trace,
ring
ring
offhook
idle −→ count1 −→ count2 −→ idle · · ·
A trace represents the state response together with the input sequence that triggers
it. This trace describes the behavior of the answering service when someone picks
up a telephone extension after two rings.
Lee & Varaiya, Signals and Systems
101
3.2. FINITE STATE MACHINES
A more elaborate trace illustrates the behavior of the answering service when it
takes a message:
ring
ring
ring
idle −→ count1 −→ count2 −→ play greeting
(3.6)
end greeting
−→
end message
recording
−→
idle
···
A state machine also produces outputs. In Figure 3.1, the output alphabet is
Outputs = {answer, record, recorded, absent}.
An output symbol is produced as part of a reaction. The output symbol that is produced
is indicated after a slash on an arc. If the arc annotation shows no output symbol, then the
output symbol is absent.
Example 3.4: The output sequence for the trace (3.6) is
(absent, absent, answer, record, recorded, · · · ).
There is an output symbol for every input symbol, and some of the output symbols
are absent.
It should be clear how to obtain the state response and output sequence for any input
sequence. We begin in the initial state and then follow the state transition diagram to
determine the successive state transitions for successive input symbols. Knowing the
sequence of transitions, we also know the sequence of output symbols.
Shorthand
State transition diagrams can get very verbose, with many arcs with complicated labels.
A number of shorthand options can make a diagram clearer by reducing the clutter.
• If no guard is specified on an arc, then that transition is always taken when the state
machine reacts and is in the state from which arc emerges, as long as the input is
102
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
not the stuttering symbol. That is, giving no guard is equivalent to giving the entire
set Inputs as a guard, minus the stuttering symbol. The stuttering symbol, recall,
always triggers a transition back to the same state, and always produces a stuttering
symbol on the output.
• Any clear notation for specifying subsets can be used to specify guards. For ex-
ample, if Inputs = {a, b, c}, then the guard {b, c} can be given by ¬a (read “not
a”).
• An else transition for a state need not be given explicitly. It is an implied self-loop
if it is not given. This is why it is shown with a dashed line in Figure 3.2.
• The output symbol is the stuttering symbol of Outputs if it is not given.
These shorthand notations are not always a good idea. For example, the else transitions
often correspond to exceptional (unexpected) input sequences, and staying in the same
state might not be the right behavior. For instance, in Figure 3.1, all else transitions are
shown explicitly, and all exceptional input sequences result in the machine ending up in
state idle. This is probably reasonable behavior, allowing the machine to recover. Had
we left the else transitions implicit, we would likely have ended up with less reasonable
behavior. Use your judgment in deciding whether or not to explicitly include else transi-
tions.
3.2.2
Update table
An alternative way to describe a finite state machine is by an update table. This is simply
a tabular representation of the state transition diagram.
For the diagram of Figure 3.1, the table is shown in Figure 3.3. The first column lists the current state. The remaining columns list the next state and the output symbol for each o