13. Draw a deterministic FSM that recognizes strings of 1’s and 0’s specified by each of the following criteria. Each FSM should reject any characters that are not 0 or 1. *

(a) The string of three characters, 101.

(b) All strings of arbitrary length that end in 101. For example, the FSM should accept 1101 but reject 1011.

(c) All strings of arbitrary length that begin with 101.

For example, the FSM should accept 1010 but reject 0101.

(d) All strings of arbitrary length that contain a 101 at least once anywhere. For example, the FSM should accept all the strings mentioned in parts (a), (b), and (c), as well as strings such as 11100001011111100111.

Transcribed Image Text:

FIGURE 7.51 The FSMs for Exercise 11. (w a a *(a) (W) b b (b) a X W X W b a Z (c) (z) (d)