Section 9.3 Finite-State Machines
753
18. Whenever a video disk is inserted into a DVR, the machine automatically turns on and plays the disk. At
the end of the recorded part of the disk, the machine turns off. To program the DVR, you must manually
turn it on and then select the menu function; when you are finished, you turn the machine off, but its timer
is set. At the appropriate time, the machine records, then at the appropriate time it turns itself completely
off. Draw the state graph for a finite-state machine that describes the behavior of the DVR.
19. You have an account at First National Usury Trust (FNUT) and a card to operate their ATM (automated
teller machine). Once you have inserted your card, the ATM will allow you to process a transaction only
if you enter your correct code number, which is 417. Draw the state graph for a finite-state machine designed to recognize this code number. The output alphabet should have three symbols: “bingo” (correct
code), “wait” (correct code so far), and “dead” (incorrect code). The input alphabet is 50, 1, 2, … , 96.
To simplify notation, you may designate an arc by I−536, for example, meaning that the machine will
take this path for an input symbol that is any digit except 3. (At FNUT, you get only one chance to enter
the code correctly.)
20. An elevator in a three-story building services floors 1, 2, and 3. Input consists of a signal to the elevator
of an up-or-down request (U or D) together with the floor from which the signal originates. The elevator
responds to an input signal by moving to the correct floor. For example, when the elevator is on floor 1
and receives a D-3 signal, it moves to floor 3. Draw a state graph for a finite-state machine that describes
the elevator behavior.
For Exercises 21–24, determine whether the given machine recognizes the given input string.
21. 11010
s 0
s 1
s 2
0
0
0
1
1
1
22. 01110111
s 0
s 1
0
0
1
1
0
1
s 2
23. 0101
s 0
s 1
s 2
0, 1
0
0
1
1
24. 01101
s 0
s 1
s 3
s 2
0, 1
0
0
0
1
1
1
For Exercises 25–28, construct finite-state machines that act as recognizers for the input described by producing an output of 1 exactly when the input received to that point matches the description. The input and output
alphabet in each case is 50, 16.
753
18. Whenever a video disk is inserted into a DVR, the machine automatically turns on and plays the disk. At
the end of the recorded part of the disk, the machine turns off. To program the DVR, you must manually
turn it on and then select the menu function; when you are finished, you turn the machine off, but its timer
is set. At the appropriate time, the machine records, then at the appropriate time it turns itself completely
off. Draw the state graph for a finite-state machine that describes the behavior of the DVR.
19. You have an account at First National Usury Trust (FNUT) and a card to operate their ATM (automated
teller machine). Once you have inserted your card, the ATM will allow you to process a transaction only
if you enter your correct code number, which is 417. Draw the state graph for a finite-state machine designed to recognize this code number. The output alphabet should have three symbols: “bingo” (correct
code), “wait” (correct code so far), and “dead” (incorrect code). The input alphabet is 50, 1, 2, … , 96.
To simplify notation, you may designate an arc by I−536, for example, meaning that the machine will
take this path for an input symbol that is any digit except 3. (At FNUT, you get only one chance to enter
the code correctly.)
20. An elevator in a three-story building services floors 1, 2, and 3. Input consists of a signal to the elevator
of an up-or-down request (U or D) together with the floor from which the signal originates. The elevator
responds to an input signal by moving to the correct floor. For example, when the elevator is on floor 1
and receives a D-3 signal, it moves to floor 3. Draw a state graph for a finite-state machine that describes
the elevator behavior.
For Exercises 21–24, determine whether the given machine recognizes the given input string.
21. 11010
s 0
s 1
s 2
0
0
0
1
1
1
22. 01110111
s 0
s 1
0
0
1
1
0
1
s 2
23. 0101
s 0
s 1
s 2
0, 1
0
0
1
1
24. 01101
s 0
s 1
s 3
s 2
0, 1
0
0
0
1
1
1
For Exercises 25–28, construct finite-state machines that act as recognizers for the input described by producing an output of 1 exactly when the input received to that point matches the description. The input and output
alphabet in each case is 50, 16.