732
Modeling Arithmetic, Computation, and Languages
A moment’s thought shows us that we can encounter four cases in adding the
digits in any given column, and we will use states of the machine to represent
these cases.
• The output should be 0 with no carry—state s 0 .
• The output should be 0 but with a carry to the next column—state s 1 .
• The output should be 1 with no carry—state s 2 .
• The output should be 1 with a carry to the next column—state s 3 .
State s 0 , as always, is the starting state. We have already indicated the output for
each state, but we need to determine the next state based on the present state and
the input. For example, suppose we are in state s 1 and the input is 11. The output
for the present state is 0, but there is a carry, so in the next column we are adding
1 + 1 + 1, which results in an output of 1 and a carry. The next state is s 3 .
PrACtiCe 46 In the binary adder under construction:
a. What is the next state if the present state is s 2 and the input is 11?
b. What is the next state if the present state is s 3 and the input is 10?
■
After considering all possible cases, we have the complete state graph of
Figure 9.5.
figure 9.5
The operation of this machine in adding the two numbers 011 and 101 (read right
to left, that is, low-order digits first) can be traced as follows:
time
t 0 t 1 t 2 t 3 t 4
Input
11 10 01 00 –
State
s 0 s 1 s 1 s 1 s 2
Output
0
0
0
0 1
Modeling Arithmetic, Computation, and Languages
A moment’s thought shows us that we can encounter four cases in adding the
digits in any given column, and we will use states of the machine to represent
these cases.
• The output should be 0 with no carry—state s 0 .
• The output should be 0 but with a carry to the next column—state s 1 .
• The output should be 1 with no carry—state s 2 .
• The output should be 1 with a carry to the next column—state s 3 .
State s 0 , as always, is the starting state. We have already indicated the output for
each state, but we need to determine the next state based on the present state and
the input. For example, suppose we are in state s 1 and the input is 11. The output
for the present state is 0, but there is a carry, so in the next column we are adding
1 + 1 + 1, which results in an output of 1 and a carry. The next state is s 3 .
PrACtiCe 46 In the binary adder under construction:
a. What is the next state if the present state is s 2 and the input is 11?
b. What is the next state if the present state is s 3 and the input is 10?
■
After considering all possible cases, we have the complete state graph of
Figure 9.5.
figure 9.5
The operation of this machine in adding the two numbers 011 and 101 (read right
to left, that is, low-order digits first) can be traced as follows:
time
t 0 t 1 t 2 t 3 t 4
Input
11 10 01 00 –
State
s 0 s 1 s 1 s 1 s 2
Output
0
0
0
0 1