Intuitively, the theorem simply states that B can match every move of A and produce
the same output sequence. It also implies that if B cannot produce a particular output
sequence, then neither can A. This is stated formally in the following corollary.
Corollary Let B simulate A. Then if
(x, y) /
∈ BehaviorsB
Lee & Varaiya, Signals and Systems
119
3.4. SIMULATION RELATIONS
then
(x, y) /
∈ BehaviorsA.
The theorem and corollary are useful for analysis. The general approach is as follows.
We have a state machine A. We wish to show that its input-output function satisfies
some property. That is, every behavior satisfies some condition. We construct a simpler
machine B whose input-output relation satisfies the same property, and where B simulates
A. Then the theorem guarantees that A will satisfy this property, too. That is, since all
behaviors of B satisfy the property, all behaviors of A must also. This technique is useful
since it is often easier to understand a simple state machine than a complex state machine
with many states.
Conversely, if there is some property that we must assure that no behavior of A has, it is
sufficient to find a simpler machine B which simulates A and does not have this property.
This scenario is typical of a safety problem, where we must show that dangerous outputs
from our system are not possible.
Example 3.17: For the parking meter of Figure 3.6, for example, we can use the
nondeterministic machine to show that if a coin is inserted at step n, the output
symbol at steps n and n + 1 is safe. By the corollary, this is sufficient to show that
the deterministic machine cannot do any differently. We do not have to directly
consider the deterministic machine.
It is important to understand what the theorem says, and what it does not say. It does
not say, for example, that if BehaviorsA ⊂ BehaviorsB then B simulates A. In fact, this
statement is not true. Consider the two machines in Figure 3.9, where
Inputs = {1, absent},
Outputs = {0, 1, absent}.
These two machines have the same behaviors. The non-stuttering output symbols are
(1, 0) or (1, 1), selected nondeterministically, assuming the input sequence has at least
two non-stuttering symbols. However, (b) does not simulate (a). The two machines are
not equivalent despite the fact that their input/output behaviors are the same.
120
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
To see this, we play the matching game. Machine (a) is allowed to move first. Ignoring
stuttering, it has no choice but to move from a to b and produce output symbol 1. Machine
(b) can match this two ways; it has no basis upon which to prefer one way to match it over
another, so it picks one, say moving to state f . Now it is the turn of machine (a), which
has two choices. If it choses to move to d, then machine (b) cannot match its move. (A
similar argument works if (b) picks state h.) Thus, machine (b) does not simulate machine
(a), despite the fact that BehaviorsA ⊂ BehaviorsB.2
3.5
Summary
State machines are models of systems whose input and output signal spaces consist of se-
quences of symbols. There are three ways of defining state machines: sets and functions,
state transition diagram, and the update table. The state machine model gives a step-by-
step procedure for evaluating the output signal. This is a state-determined system: once
we know the current state, we can tell the future behavior for any future input symbols.
A state machine can be non-deterministic: given the current state and current input sym-
bol, it may have more than one possible next state and current output symbol. Non-
determistic machines typically arise through abstraction of deterministic machines. Two
state machines, with the same input and output alphabets, may be related through simula-
tion. Simulation is used to understand properties of the behavior of one machine in terms
of the behaviors of another (presumably simpler) machine.
2Recall that in our notation ⊂ allows the two sets to be equal.
Lee & Varaiya, Signals and Systems
121
3.5. SUMMARY
{ absent}
{ absent}
{ ring }
else
count1
count2
{ ring }
{ ring } /answer
idle
else
play
greeting
else
{ absent}
else
{ end greeting } /record
record
else
ing
{ end message, offhook } /recorded
{ absent}
states
idle: nothing is happening
count1: one ring has arrived
count2: two rings have arrived
play greeting: playing the greeting message
recording : recording the message
inputs
ring - incoming ringing signal
offhook - a telephone extension is picked up
end greeting - greeting message is finished playing
end message - end of message detected (e.g. dialtone)
absent - no input of interest.
outputs
answer - answer the phone and start the greeting message
record - start recording the incoming message
recorded- recorded an incoming message
absent - default output when there is nothing interesting to say
Figure 3.1: State transition diagram for a telephone answering service.
122
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
else
guard1/output1
state
guard2/output2
initial state indicator
state machine:
(States, Inputs, Outputs, update, initialState)
update : States × Inputs → States × Outputs
initialState ∈ States
elements:
state ∈ States
output1, output2 ∈ Outputs
guard1, guard2 ⊂ Inputs
else = {i ∈ Inputs | i /
∈ (guard1 ∪ guard2)}
determinacy: (There is at most one possible reaction to an input symbol)
guard1 ∩ guard2 = /0
Figure 3.2: Summary of notation in state transition diagrams, shown for a single
state with two outgoing arcs and one self loop.
Lee & Varaiya, Signals and Systems
123
3.5. SUMMARY
current
(next state, output symbol) under specified input symbol
state
ring
offhook
end greeting
end message
absent
idle
(count1,
(idle,
(idle,
(idle,
(idle,
absent)
absent)
absent)
absent)
absent)
count1
(count2,
(idle,
(idle,
(idle,
(count1,
absent)
absent)
absent)
absent)
absent)
count2
(play greeting,
(idle,
(idle,
(idle,
(count2,
answer)
absent)
absent)
absent)
absent)
play greeting (idle,
(idle,
(recording,
(idle,
(play greeting,
absent)
absent)
record)
absent)
absent)
recording
(idle,
(idle,
(idle,
(idle,
(recording,
absent)
recorded)
absent)
recorded)
absent)
Figure 3.3: Update table for the telephone answering service specifies next state
and current output symbol as a function of current state and current input symbol.
{0}
{1}
{1}
{1}
start
1
11
{0}
{0}
{1}
110
{0}/ recognize
Figure 3.4: A machine that implements CodeRecognizer . It outputs recognize at
the end of every input subsequence 1100, otherwise it outputs absent.
124
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
{1}/1
{0}/0
{0,1}/1
a
b
{0}/0
Figure 3.5: A simple nondeterministic state machine.
{ coin25}/ safe
{ coin25}/ safe
{ coin5,
{ coin5} { coin25}
coin25}/
{ tick}/
{ coin5}/
{ coin5}/ safe
{ coin5}/ safe
/ safe
/ safe
safe
expired
safe
0
1
...
5
...
25
...
60
{ tick}/ expired
{ tick}/ safe
{ tick}/ safe
{ tick}/ safe
(a)
{ coin5, coin25} / safe
{ coin5, coin25, tick} /
{ tick}/
{ coin5, coin25} /
safe
expired
safe
0
1
more
{ tick}/ expired
{ tick}/ safe
(b)
Figure 3.6: Deterministic and nondeterministic models for a 60 minute parking
meter.
Lee & Varaiya, Signals and Systems
125
3.5. SUMMARY
{1}/1
1
2
{1}/1
{1}/0
0
3
(a)
{1}/0
{1}/1
5
4
{1}/1
{1}/1
1and4
{1}/1
0and3
{1}/1
0
1to5
{1}/1
2and5
{1}/0
{1}/0
(c)
(b)
Figure 3.7: Three state machines where (a) and (b) simulate one another and (c)
simulates (a) and (b).
126
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
{1}/0
{1}/1
{1}/0
0
1
2
3
{1}/1
{1}/0
{1}/1
(a)
{1}/0
{1}/0
{1}/1
0and2
1and3
0to3
{1}/1
(b)
(c)
Figure 3.8: Three state machines where (a) and (b) simulate each other and (c)
simulates (a) and (b)
Lee & Varaiya, Signals and Systems
127
3.5. SUMMARY
{1} / 1
c
{1} / 1
a
b
d
{1} / 0
(a)
{1} / 1
{1} / 1
f
g
e
{1} / 0
h
i
{1} / 1
(b)
Figure 3.9: Two state machines with the same behaviors where (b) does not
simulate (a).
128
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
Exercises
In some of the following exercises you are asked to design state machines that carry
out a given task. The design is simple and elegant if the state space is properly chosen.
Although the state space is not unique, there often is a natural choice. As usual, each
problem is annotated with the letter E, T, C which stands for exercise, requires some
thought, requires some conceptualization. Problems labeled E are usually mechanical,
those labeled T require a plan of attack, those labeled C usually have more than one
defensible answer.
1. E A state machine with
Inputs = {a, b, c, d, absent},
has a state s with two emerging arcs with guards
guard1 = {a}
and
guard2 = {a, b, d}.
(a) Is this state machine deterministic?
(b) Define the set else for state s and specify the source and destination state for
the else arc.
2. E For the answering service example of figure 3.1, assume the input sequence is
(offhook, offhook, ring, offhook, ring, ring, ring, offhook, · · · ).
This corresponds to a user of the answering service making two phone calls, an-
swering a third after the first ring, and answering a second after the third ring.
(a) Give the state response of the answering service.
(b) Give the trace of the answering service.
(c) Give the output sequence.
3. E Consider the alphabets
Inputs = Outputs = Binary = {0, 1}.
Note that there is no stuttering input or output symbols here. This simplifies the
notation in the problem somewhat.
Lee & Varaiya, Signals and Systems
129
EXERCISES
(a) Construct a state machine that uses these alphabets such that given any input
sequence (x(0), x(1), · · · ) without stuttering symbols, the output sequence is
given by, ∀ n ∈ N0,
1
if n ≥ 2 ∧ (x(n − 2), x(n − 1), x(n)) = (1, 1, 1)
y(n) =
0
otherwise
In words, the machine outputs 1 if the current input symbol and the two pre-
vious input symbols are all 1’s, otherwise it outputs 0. (Had we included a
stuttering symbol, the above equation would be a bit more complicated.)
(b) For the same input and output alphabet, construct a state machine that out-
puts 1 if the current input symbol and two previous input symbols are either
(1, 1, 1) or (1, 0, 1), and otherwise it outputs 0.
4. E A modulo N counter is a device that can output any integer between 0 and
N − 1. The device has three input symbols, increment, decrement, and reset, plus,
as always, a stuttering symbol absent; increment increases the output integer by 1;
decrement decreases this integer by 1; and reset sets the output symbol to 0. Here
increment and decrement are modulo N operations.
Note: Modulo N numbers work as follows. For any integer m, m mod N = k where
0 ≤ k ≤ N − 1 is the unique integer such that N divides (m − k). Thus there are only
N distinct modulo-N numbers, namely, 0, · · · , N − 1.
(a) Give the state transition diagram of this counter for N = 4.
(b) Give the update table of this counter for N = 4.
(c) Give a description of the state machine by specifying the five entities that
appear in (3.1); again assume N = 4.
(d) Take N = 3. Calculate the state response for the input sequence
(increment4, decrement3, · · · )
starting with initial state 1, where sn means s repeated n times.
5. T The state machine UnitDelay is defined to behave as follows. On the first non-
stuttering reaction (when the first non-stuttering input symbol arrives), the output
symbol a is produced. On subsequent reactions (when subsequent input symbols
arrive), the input symbol that arrived at the previous non-stuttering reaction is pro-
duced as an output symbol.
130
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
(a) Assume the input and output alphabets are
Inputs = Outputs = {a, b, c, absent}.
Give a finite state machine that implements UnitDelay for this input set. Give
both a state transition diagram and a definition of each of the components in
(b) Assume the input and output sets are
Inputs = Outputs = N0 ∪ {absent},
and that on the first non-stuttering reaction, the machine produces 0 instead
of a. Give an (informal) argument that no finite state machine can implement
UnitDelay for this input set. Give an infinite state machine by defining each
of the components in (3.1).
6. T Construct an infinite state machine that realizes Equal.
7. C An elevator connects two floors, 1 and 2. It can go up (if it is on floor 1), down
(if it is on floor 2) and stop on either floor. Passengers at any floor may press a
button requesting service. Design a controller for the elevator so that (1) every
request is served, and (2) if there is no pending request, the elevator is stopped.
For simplicity, do not be concerned about responding to requests from passengers
inside the elevator.
8. T The state machine in Figure 3.10 has the property that it outputs at least one
1 between any two 0’s. Construct a two-state nondeterministic state machine that
simulates this one and preserves that property.
{0}/ 1
{1}/ 0
{1}/ 1
{1}/ 1
{1}/ 1
0
1
2
3
{0}/ 1
{0}/ 1
{0}/ 1
Figure 3.10: Machine that outputs at least one 1 between any two 0’s.
Lee & Varaiya, Signals and Systems
131
EXERCISES
9. T For the nondeterministic state machine in Figure 3.11 the input and output al-
phabets are
Inputs = Outputs = {0, 1, absent}.
(a) Define the possibleUpdates function (3.9) for this state machine.
(b) Define the relation Behaviors in (3.11) for this state machine. Part of the chal-
lenge here is to find a way to describe this relation compactly. For simplicity,
ignore stuttering; i.e. assume the input symbol is never absent.
10. E The state machine in Figure 3.12 implements CodeRecognizer, but has more
states than the one in Figure 3.4. Show that the two machines simulate each other
by giving simulation relations.
11. E The state machine in Figure 3.13 has input and output alphabets
Inputs = {1, a},
Outputs = {0, 1, a},
where a (short for absent) is the stuttering symbol. State whether each of the fol-
lowing is in the set Behaviors for this machine. In each of the following, the ellipsis
{0,1}/1
{1}/1
B
{0}/0
A
{0,1}/0
C
{1}/0
Figure 3.11: Nondeterministic state machine for Exercise 9.
132
Lee & Varaiya, Signals and Systems
3. STATE MACHINES
“· · · ” means that the last symbol is repeated forever. Also, in each case, the input
and output signals are given as sequences.
(a) ((1, 1, 1, 1, 1, · · · ), (0, 1, 1, 0, 0, · · · ))
{0}
{1}
{1}
{1}
start
1
11
{0}
{0}
{1}
110
{0}/ recognize
{1}
1100
{0}
Figure 3.12: A machine that implements CodeRecognizer , but has more states
than the one in Figure 3.4.
{1} / 1
{1} / 0
{1} / 0
a
b
c
Figure 3.13: State machine for problem 11.
Lee & Varaiya, Signals and Systems
133
EXERCISES
(b) ((1, 1, 1, 1, 1, · · · ), (0, 1, 1, 0, a, · · · ))
(c) ((a, 1, a, 1, a, · · · ), (a, 1, a, 0, a, · · · ))
(d) ((1, 1, 1, 1, 1, · · · ), (0, 0, a, a, a, · · · ))
(e) ((1, 1, 1, 1, 1, · · · ), (0, a, 0, a, a, · · · ))
12. E The state machine in Figure 3.14 has
Inputs = {1, absent},
Outputs = {0, 1, absent}.
Find a state machine with only two states that simulates the one in Figure 3.14 and
that is simulated by the one in Figure 3.14, and give the simulation relations.
13. E You are told that state machine A has
Inputs = {1, 2, absent},
Outputs = {1, 2, absent},
States = {a, b, c, d}.
but you are told nothing further. Do you have enough information to construct a
state machine B that simulates A? If so, give such a state machine, and the simula-
tion relation.
{1} / 1
{1} / 0
b
a
c
d
{1} / 0
{1} / 1
Figure 3.14: A machine that has more states than it needs.
1