Section 9.3 Finite-State Machines
731
PrACtiCe 43 For the machine M of Example 29, what output sequence is produced by the input sequence
11001?
PrACtiCe 44 A machine M is given by the state graph of Figure 9.4. Give the state table for M.
figure 9.4
■
■
■
The machine of Example 29 is not particularly interesting. If finite-state machines model real-world computers, they should be able to do something. Let’s try
to build a finite-state machine that will add two binary numbers. The input will
consist of a sequence of pairs of binary digits, each of the form 00, 01, 10, or 11.
Each pair represents one column of digits of the two numbers to be added, least
significant digits first (so in this particular case, read the inputs column by column
right to left). Thus to add the two numbers
011
101
the number pairs are 11, 10, and 01. The output gives the least significant digits of
the answer first. Recall the basic facts of binary addition:
0 0 1
1
0 1 0
1
0 1 1 10
(Note that in the fourth addition a carry to the next column takes place.)
PrACtiCe 45 A machine M is described by the state table shown in Table 9.2.
a. Draw the state graph for M.
b. What output corresponds to an input sequence of 2110?
table 9.2
present state
next state
output
present input
0 1 2
s 0
s 0 s 1 s 1
0
s 1
s 1 s 0 s 0
1
731
PrACtiCe 43 For the machine M of Example 29, what output sequence is produced by the input sequence
11001?
PrACtiCe 44 A machine M is given by the state graph of Figure 9.4. Give the state table for M.
figure 9.4
■
■
■
The machine of Example 29 is not particularly interesting. If finite-state machines model real-world computers, they should be able to do something. Let’s try
to build a finite-state machine that will add two binary numbers. The input will
consist of a sequence of pairs of binary digits, each of the form 00, 01, 10, or 11.
Each pair represents one column of digits of the two numbers to be added, least
significant digits first (so in this particular case, read the inputs column by column
right to left). Thus to add the two numbers
011
101
the number pairs are 11, 10, and 01. The output gives the least significant digits of
the answer first. Recall the basic facts of binary addition:
0 0 1
1
0 1 0
1
0 1 1 10
(Note that in the fourth addition a carry to the next column takes place.)
PrACtiCe 45 A machine M is described by the state table shown in Table 9.2.
a. Draw the state graph for M.
b. What output corresponds to an input sequence of 2110?
table 9.2
present state
next state
output
present input
0 1 2
s 0
s 0 s 1 s 1
0
s 1
s 1 s 0 s 0
1