determine as much as possible about the output symbols. You can try the state machines
in any order. Given what you learn about the output symbols, then update what you know
about the feedback input symbols, and repeat the process, trying each state machine again.
Repeat this process until all signal values are specified, or until you learn nothing more
about the output symbols. We illustrate the procedure in an example involving only one
machine, but keep in mind that the procedure works for any number of machines.
{0}/(0,1)
{1}/(1,1)
{0}/(0,0)
a
b
{0, 1, absent}
{ react, absent}
{1}/(1,0)
A
{0, 1, absent}
Figure 4.20: Feedback composition without state-determined output.
Lee & Varaiya, Signals and Systems
171
4.7. FEEDBACK
Example 4.9: Figure 4.20 shows a feedback composition without state-determined
output. Nonetheless, our constructive procedure can be used to find a unique fixed
point for each reaction. Suppose that the current state is a, and that the input to the
composition is react. Begin by assuming that the symbol on the feedback connec-
tion is unknown. Try component machine A (this is the only component machine in
this example, but if there were more, we could try them in any order). Examining
machine A, we see that in its current state, a, the output symbol cannot be fully
determined. Thus, this machine does not have state-determined output. However,
more careful examination reveals that in state a, the second element of the output
tuple is determined. That second element has value 1. Fortunately, this changes the
value on the feedback connection from unknown to 1.
Now we repeat the procedure. We choose a state machine to try. Again, there is
only one state machine in this example, so we try A. This time, we know that the
input symbol is 1, so we know that the machine must take the transition from a to
b and produce the output tuple (1, 1). This results in all symbols being known for
the reaction, so we are done evaluating the reaction.
Now assume the current state is b. Again, the feedback symbol is initially unknown,
but once again, trying A, we see that the second element of the output tuple must be
0. Thus, we change the feedback symbol from unknown to 0 and try the machine
again. This time, its input is 0, so it must take the self loop back to b and produce
the output tuple (0, 0).
Recall that the set Behaviors is the set of all (x, y) such that x is an input sequence
and y is an output sequence. For this machine, ignoring stuttering, the only pos-
sible input sequence is (react, react, react, · · · ). We have just determined that the
resulting output sequence is (1, 0, 0, 0, · · · ). Thus, ignoring stuttering,
Behaviors = {((react, react, react, · · · ), (1, 0, 0, 0, · · · ))}.
Of course, we should take into account stuttering, so this set needs to be augmented
with all (x, y) pairs that look like the one above but have stuttering symbols inserted.
This procedure can be applied in general to any composition of state machines. If the
procedure can be applied successfully (nothing remains unknown) for all reachable states
172
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
of the composition, then the composition is well-formed. The following example applies
the procedure to a more complicated example.
Example 4.10:
We add more detail to the message recorder in Figure 4.9. In
particular, as shown in Figure 4.21, we wish to model the fact that the message
recorder stops recording when either it detects a dialtone or when a timeout period is
greeting playback
device
{ answer}
{ end greeting}
{ light on, light off}
{ recorded message}
AnsweringMachine
light
{ ring, offhook}
{ play}
Playback
play
button
{ record}
{ end message}
{ done playing}
{ play messages}
telephone
{ dialtone}
MessageRecorder
line interface
message playback
{ start recording}
device
{ timeout}
recording device
Figure 4.21: Answering machine composition with feedback. The absent ele-
ments are not shown (to reduce clutter).
Lee & Varaiya, Signals and Systems
173
4.7. FEEDBACK
reached. This is modeled by a two-state finite state machine, shown in Figure 4.22.
Note that this machine does not have state-determined output. For example, in state
idle, the output could be (absent, start recording) or it could be (absent, absent)
when the input is not the stuttering input.
The MessageRecorder and AnsweringMachine state machines form a feedback
loop. Let us verify that composition is well-formed. First, note that in the idle
state of the MessageRecorder, the upper output symbol is known to be absent (see
Figure 4.22). Thus, only in the recording state is there any possibility of a prob-
lem that would lead to the composition being ill-formed. In that state, the output
symbol is not known unless the input symbols are known. However, notice that
the recording state is entered only when a record input symbol is received. In Fig-
ure 4.6, you can see that the record value is generated only when entering state
record message. But in all arcs emerging from that state, the lower output sym-
bol of AnsweringMachine will always be absent; the input symbol does not need
to be known to know that. Continuing this reasoning by considering all possible
state transitions from this point, we can convince ourselves that the feedback loop
is well-formed.
The sort of reasoning in this more complicated example is difficult and error-prone for
even moderate compositions of state machines. It is best automated. Compilers for syn-
chronous languages do exactly this. Successfully compiling a program involves proving
that feedback loops are well-formed.
{ record, absent}
{( record, absent, absent)}/
{ end message,
( absent, start recording)
absent}
else
{ dialtone, absent}
idle
recording
else
{ timeout, absent}
{( absent, dialtone, absent), ( absent, absent, timeout),
{ start recording,
( absent, dialtone, timeout)}/
absent}
( end message, absent)
Figure 4.22: Message recorder subsystem of the answering system.
174
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
4.7.5
Exhaustive search
If a feedback composition has one or more machines with state-determined output, then
finding a unique fixed point is easy. Without such state-determined output, we can apply
the procedure in the previous section. Unfortunately, if the procedure fails, we cannot
conclude that the composition is ill-formed. The procedure fails for example 4.7, shown
in Figure 4.17, despite the fact that this example is well-formed. For that example, we can
determine the unique fixed point by exhaustive search. That is, for each reachable state
of the composition, and for each possible input to the composition, we try all possible
transitions out of the current states of the component machines. We reject those that lead
to a contradiction. For example, in Figure 4.17, assuming the current state is 1, the output
of the component machine cannot be maybe because then the input would have to be
maybe, which would result in the output being absent. If after rejecting all contradictions
there remains exactly one possibility in each reachable state, then the composition is well-
formed.
Exhaustive search works in Figure 4.17 only because the number of reachable states is
finite and the number of transitions out of each state is finite. If either of these conditions
is violated, then exhaustive search will not work. Thus, there are state machine that when
put in a feedback loop are well-formed, but where there is no constructive procedure for
evaluating a reaction (see box on page 176). Even when exhaustive search is theoretically
possible, in practice the number of possibilities that must be tried grows extremely fast.
4.7.6
Nondeterministic machines
Nondeterministic state machines can be composed just as deterministic state machines
are composed. In fact, since deterministic state machines are a special case, the two types
of state machines can be mixed in a composition. Compositions without feedback are
straightforward, and operate almost exactly as described above (see exercises 14 and 15).
Compositions with feedback require a small modification to our evaluation process.
Recall that to evaluate the reaction of a feedback composition, we begin by setting to
unknown any input symbols that are not initially known. We then proceed through a series
of rounds where in each round, we attempt to determine the output symbols of the state
machines in the composition given what we know about the input symbols. After some
number of rounds, no more information is gained. At this point, if all of the input and
Lee & Varaiya, Signals and Systems
175
4.7. FEEDBACK
Probing Further: Constructive Semantics
The term “semantics” means meaning. We have defined the meaning of compositions
of state machines using the notion of synchrony, which makes feedback compositions
particularly interesting. When we define “well-formed,” we are, in effect, limiting the
compositions that are valid. Compositions that are not well-formed fall outside our
synchronous semantics. They have no meaning.
One way to define the semantics of a composition is to give a procedure for evaluating
the composition (the resulting procedure is called an operational semantics). We have
given three successively more difficult procedures for evaluating a reaction of a com-
position of state machines with feedback. If at least one machine in each directed loop
has state-determined output, then it is easy to evaluate a reaction. If not, we can apply
the constructive procedure of section 4.7.4. However, that procedure may result in some
feedback connections remaining unknown even though the composition is well-formed.
The ultimate procedure is exhaustive search, as described in section 4.7.5. However,
exhaustive search is not always possible, and even when it is theoretically possible, the
number of possibilities to explore may be so huge that it is not practical. There are state
machines that when put in a feedback loop are well-formed, but where there is no con-
structive procedure for evaluating a reaction, and no constructive way to demonstrate
that they are well-formed. Thus, there is no operational semantics for our feedback
compositions.
This situation is not uncommon in computing and in mathematics. Kurt Gödel’s
famous incompleteness theorem (1931), for example, states (loosely) that in any formal
logical system, there are statements that are true but not provable. This is analogous in
that we can have feedback compositions that are well-formed, but we have no procedure
that will always work to demonstrate that they are well-formed. Around the same time,
Alan Turing and Alonzo Church demonstrated that there are functions that cannot be
computed by any procedure.
To deal with this issue, Gerard Berry has proposed that synchronous composition have
a constructive semantics, which means precisely that well-formed compositions are
defined to be those for which the constructive procedure of Section 4.7.4 works. When
that procedure fails, we simply declare the composition to be unacceptable. This is prag-
matic solution, and in many situations, it is adequate. See G. Berry, The Constructive
Semantics of Pure Esterel, Book Draft, http://www-sop.inria.fr/meije/esterel/doc/main-
papers.html.
176
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
output symbols are known, then the composition is well-formed. This procedure works
for most (but not all) well-formed compositions.
This process needs to be modified slightly for nondeterministic machines because in each
reaction, a machine may have several possible output symbols and several possible next
states. For each machine, at each reaction, we define the sets PossibleInputs ⊂ Inputs,
PossibleNextStates ⊂ States and PossibleNextOutputs ⊂ Outputs. If the inputs to a partic-
ular machine in the composition are known completely, then PossibleInputs has exactly
one element. If they are completely unknown, then PossibleInputs is empty.
The rounds proceed in a similar fashion to before. For each state machine in the com-
position, given what is known about the input symbols, i.e. given PossibleInputs, deter-
mine what you can about the next state and output symbols. This may result in elements
being added to PossibleNextStates and PossibleNextOutputs. When a round results in
no such added elements, the process has converged. If none of the PossibleInputs or
PossibleOutputs sets is empty, then the composition is well-formed.
4.8
Summary
Many systems are designed as state machines. Usually the design is structured by com-
posing component state machines. In this chapter, we considered synchronous composi-
tion. Feedback composition proves particularly subtle because the input symbol of a state
machine in a reaction may depend on its own output symbol in the same reaction. We call
a feedback composition well-formed if every signal has a unique non-stuttering symbol
in each reaction.
Describing systems as compositions of state machines helps in many ways. It promotes
understanding. The block diagram syntax that describes the structure often shows that
individual components are responsible for distinct functions of the overall system. Some
components may already be available and so we can reuse their designs. The design of the
answering machine in Figure 4.9 takes into account the availability of the telephone line
interface, recording device, etc. Composition also simplifies description; once we specify
the component state machines and the composition, the overall state machine is auto-
matically defined by the rules of composition. Compilers for synchronous programming
languages and tools for verification do this automatically.
We have three successively more difficult procedures for evaluating a reaction of a com-
position of state machines with feedback. If at least one machine in each directed loop
Lee & Varaiya, Signals and Systems
177
4.8. SUMMARY
has state-determined output, then it is easy to evaluate a reaction. If not, we can apply the
constructive procedure of section 4.7.4. But that procedure may be inconclusive. The ul-
timate procedure is exhaustive search, as described in section 4.7.5. However, exhaustive
search is not always possible, and even when it is theoretically possible, the number of
possibilities to explore may be so huge that it is not practical.
178
Lee & Varaiya, Signals and Systems
4. COMPOSING 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 simplified and elegant if the state space is properly chosen.
Although the state space is not unique, there often is a natural choice. 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 Define the composite state machine in Figure 4.7 in terms of the component
machines, as done for the simpler compositions in figures 4.3 and 4.1. Be sure to state any required assumptions.
2. E Define the composite state machine in Figure 4.10 in terms of the component
machines, as done for the simpler compositions in figures 4.3 and 4.1. Be sure to state any required assumptions. Give the definition in two different ways:
(a) Directly form a product of the three state spaces.
(b) First compose the A and B state machines to get a new D state machine, and
then compose D with C.
(c) Comment on the relationship between the models in part (a) and (b).
3. T Consider the state machine UnitDelay studied in part (a) of exercise 5 at the end
of the previous chapter.
(a) Construct a state machine model for a cascade composition of two such ma-
chines. Give the sets and functions model (it is easier than the state transition
diagram or table).
(b) Are all of the states in the state space of your model in part (a) reachable? If
not, give an example of an unreachable state.
(c) Give the state space (only) for cascade compositions of three and four unit
delays. How many elements are there in each of these state spaces?
(d) Give an expression for the size of the state space as function of the number N
of cascaded delays in the cascade composition.
4. C Consider the parking meter example of the previous chapter, example 3.1, and
the modulo N counter of Exercise 4 at the end of the previous chapter. Use these
Lee & Varaiya, Signals and Systems
179
EXERCISES
two machines to model a citizen that parks at the meter when the machines start,
and inserts 25 cents every 30 minutes, and a police officer who checks the meter
every 45 minutes, and issues a ticket if the meter is expired. For simplicity, assume
that the police office issues a new ticket each time he finds the meter expired, and
that the citizen remains parked forever.
You may construct the model at the block diagram level, as in Figure 4.9, but de-
scribe in words any changes you need to make to the designs of the previous chap-
ter. Give state transition diagrams for any additional state machines you need. How
long does it take for the citizen to get the first parking ticket?
Assume you have an eternal clock that emits an event tick every minute.
Note that the output alphabet of the modulo N counter does not match the input
alphabet of the parking meter. Neither does its input alphabet match the output al-
phabet of the parking meter. Thus, one or more intermediate state machines will be
needed to translate these alphabets. You should fully specify these state machines
(i.e., don’t just give them at the block diagram level). Hint: These state machines,
which perform an operation called renaming, only need one state.
5. C Consider a machine with
States = {0, 1, 2, 3},
Inputs = {increment, decrement, reset, absent},
Outputs = {zero, absent},
initialState = 0,
such that increment increases the state by 1 (modulo 4), decrement decreases the
state by 1 (modulo 4), reset resets the state to 0, and the output symbol is absent
unless the next state is 0, in which case the output symbol is zero. So, for example,
if the current state is 3 and the input is increment, then the new state will be 0 and
the output will be zero. If the current state is 0 and the input is decrement, then the
new state will be 3 and the output will be absent.
(a) Give the update function for this machine, and sketch the state transition dia-
gram.
(b) Design a cascade composition of two state machines, each with two states,
such that the composition has the same behaviors as the one above. Give a
diagram of the state machines and their composition, and carefully define all
the input and output alphabets.
180
Lee & Varaiya, Signals and Systems
4. COMPOSING STATE MACHINES
(c) Give a simulation relation from the single machine and the cascade compo-
sition, and a simulation relation from the cascade composition to the single
machine.
6. C A road has a pedestrian crossing with a traffic light. The light is normally green
for vehicles, and the pedestrian is told to wait. However, if a pedestrian presses a
button, the light turns yellow for 30 seconds and then red for 30 seconds. When it
is red, the pedestrian is told “cross now.” After the 30 seconds of red, the light turns
back to green. If a pedestrian presses the button again while the light is red, then
the red is extended to a full minute.
Construct a composite model for this system that has at least two state machines,
TrafficLight for the traffic light seen by the cars, and WalkLight for the walk light
seen by the pedestrians. The state of machine should represent the state of the
lights. For example, TrafficLight should have at least three states, one for green,
one for yellow, and one for red. Each color may, however, have more than one state
associated with it. For example, there may be more than one state in which the
light is red. It is typical in modeling systems for the states of the model to represent
states of the physical system.
Assume you have a timer available such that if you emit an output start timer, then
30 seconds later an input symbol timeout will appear. It is sufficient to give the state
transition graphs for the machines. State any assumptions you need to make.
7. E Suppose you are given two state machines A and B, Suppose the sizes of the
input alphabets are iA, iB, respectively, the sizes of the output alphabets are oA, oB
respectively, and the numbers of states are sA, sB, repectively. Give the sizes of the
input and output alphabets and the number of states for the following compositions:
(a) side-by-side,
(b) cascade,
(c) and feedback, where the structure of the feedback follows the pattern in Figure
8. T Example 4.2 shows a state machine in which a state is not reachable from the
initial state. Here is a recursive algorithm to calculate the reachable states for any
nondeterministic machine,
StateMachine = (States, Inputs, Outputs, possibleUpdates, initialState).
Lee & Varaiya, Signals and Systems
181