752
Modeling Arithmetic, Computation, and Languages
In Exercises 7–10, draw the state graph for the machine, and compute the output sequence for the given input
sequence.
7. 10001
present state
next state
output
present input
0
1
s 0
s 0
s 2
1
s 1
s 1
s 0
0
s 2
s 0
s 1
0
8. 0011
present state
next state
output
present input
0
1
s 0
s 2
s 3
0
s 1
s 0
s 1
1
s 2
s 1
s 3
0
s 3
s 1
s 2
1
9. acbbca
present state
next state
output
present input
a
b
c
s 0
s 1
s 1
s 1
0
s 1
s 2
s 2
s 1
0
s 2
s 0
s 2
s 1
1
10. 21021
present state
next state
output
present input
0
1
2
s 0
s 3
s 1
s 2
1
s 1
s 3
s 0
s 1
2
s 2
s 2
s 1
s 1
0
s 3
s 1
s 4
s 0
0
s 4
s 1
s 4
s 2
2
11. a. Construct a finite-state machine that complements each bit of the binary input string (read left to right).
b. Write the output for the input sequence 01011.
12. a. Construct a finite-state machine that will compute x + 1 where x is the input given in binary form, least
significant digit first (in this case, read the input right to left). You could use the binary adder of Figure
9.5 by writing 1 as 00 … 01 with the correct number of leading 0s, but that’s much too complicated.
b. Write the output for x = 1101.
13. a. Construct a finite-state machine that will compute the bitwise AND of two binary input strings.
b. Write the output for the input sequence consisting of the strings 11011 and 10010 (read left to right).
14. a. Construct a finite-state machine that will compute the bitwise OR of two binary input strings.
b. Write the output for the input sequence consisting of the strings 11011 and 10010 (read left to right).
15. a. Construct a delay machine having input and output alphabet 50, 16 that, for any input sequence a l a 2 a 3 …
produces an output sequence of 00a l a 2 a 3 … .
b. Explain (intuitively) why a finite-state machine cannot be built that, for any input sequence a l a 2 a 3 … ,
produces the output sequence 0a 1 0a 2 0a 3 … .
16. a. Construct a finite-state machine that will compute the 2’s complement of p where p is a binary number
input with the least significant digit first. (See Exercise 27, Section 8.2.) (In this case, read the input
right to left.)
b. Use the machine of part (a) to find the 2’s complement of 1100 and of 1011.
17. You are designing a Windows-based, event-driven program to handle customers for a small business.
You design the user interface with three screens. The opening screen contains an exit button to quit the
program and displays a list box of customer names. Double-clicking on one of the entries in the list box
brings up a second screen showing complete data for that customer. This screen contains a button to get
back to the opening screen. The opening screen also contains a button that brings up a form to enter the
data for a new customer. Draw the state graph for a finite-state machine that describes the high-level user
interaction with the program.
Modeling Arithmetic, Computation, and Languages
In Exercises 7–10, draw the state graph for the machine, and compute the output sequence for the given input
sequence.
7. 10001
present state
next state
output
present input
0
1
s 0
s 0
s 2
1
s 1
s 1
s 0
0
s 2
s 0
s 1
0
8. 0011
present state
next state
output
present input
0
1
s 0
s 2
s 3
0
s 1
s 0
s 1
1
s 2
s 1
s 3
0
s 3
s 1
s 2
1
9. acbbca
present state
next state
output
present input
a
b
c
s 0
s 1
s 1
s 1
0
s 1
s 2
s 2
s 1
0
s 2
s 0
s 2
s 1
1
10. 21021
present state
next state
output
present input
0
1
2
s 0
s 3
s 1
s 2
1
s 1
s 3
s 0
s 1
2
s 2
s 2
s 1
s 1
0
s 3
s 1
s 4
s 0
0
s 4
s 1
s 4
s 2
2
11. a. Construct a finite-state machine that complements each bit of the binary input string (read left to right).
b. Write the output for the input sequence 01011.
12. a. Construct a finite-state machine that will compute x + 1 where x is the input given in binary form, least
significant digit first (in this case, read the input right to left). You could use the binary adder of Figure
9.5 by writing 1 as 00 … 01 with the correct number of leading 0s, but that’s much too complicated.
b. Write the output for x = 1101.
13. a. Construct a finite-state machine that will compute the bitwise AND of two binary input strings.
b. Write the output for the input sequence consisting of the strings 11011 and 10010 (read left to right).
14. a. Construct a finite-state machine that will compute the bitwise OR of two binary input strings.
b. Write the output for the input sequence consisting of the strings 11011 and 10010 (read left to right).
15. a. Construct a delay machine having input and output alphabet 50, 16 that, for any input sequence a l a 2 a 3 …
produces an output sequence of 00a l a 2 a 3 … .
b. Explain (intuitively) why a finite-state machine cannot be built that, for any input sequence a l a 2 a 3 … ,
produces the output sequence 0a 1 0a 2 0a 3 … .
16. a. Construct a finite-state machine that will compute the 2’s complement of p where p is a binary number
input with the least significant digit first. (See Exercise 27, Section 8.2.) (In this case, read the input
right to left.)
b. Use the machine of part (a) to find the 2’s complement of 1100 and of 1011.
17. You are designing a Windows-based, event-driven program to handle customers for a small business.
You design the user interface with three screens. The opening screen contains an exit button to quit the
program and displays a list box of customer names. Double-clicking on one of the entries in the list box
brings up a second screen showing complete data for that customer. This screen contains a button to get
back to the opening screen. The opening screen also contains a button that brings up a form to enter the
data for a new customer. Draw the state graph for a finite-state machine that describes the high-level user
interaction with the program.