Finite State Machines - Exercises 1
Following are some exercises on finite state machines. You should attempt to work through these before checking the answers. For the problems in this section, draw a deterministic finite state machine which implements the specification. Some machines may be impossible to construct; explain why if you think so. Where appropriate, the alphabet (allowable input characters) for the machine is listed [in brackets]. It's not important to be precise about every transition; it is sufficient to draw an unadorned arrow to mean "all other characters". Remember to indicate the starting state. 1. Consider machines which accept a stream of 1 or more bits (the alphabet is limited to 1's and 0's), and whose output is 1 (accepting) or 0 (rejecting). Construct FSMs which implement the following operations:
c_{1} ||
c_{2} ||
... || c_{i}
(b) and
(c) xor
2. (a) Accepts just the string
MURMUR by itself. [MRU]
(b) Accepts CYBOT followed by any characters.
[BCOTY]
(c) Accepts FROG with any prefix. [FGOR]
(d) Accepts any string containing FROG. [FGOR]
(e) Accepts any string containing MURMURS. [MRSU]
(f) Accepts strings consisting of only 0 or more repetitions of 15211. [125]
(g) Accepts strings starting with 0 or more repetitions of 15211. [125]
(all strings start with 0 or more repetitions of 15211.) 3. (a) Accepts CAT or DOG alone. [ACDGOT]
(b) Accepts strings containing CAT or DOG anywhere. [ACDGOT]
(c) Accepts strings containing ART or ARC anywhere. [ACRT]
(d) Accepts strings which are any of ART or ARTS or ARTIST or ABLE. [ABEILRST]
What does this remind you of?
4. #c means the number of character c occuring in the string. (a) Accepts strings of even length. [AB]
(b) Accepts strings with exactly 3 A's. [AB]
(c) Accepts strings with at least 3 A's. [AB]
(d) Accepts strings where #a > #b. [AB]
(e) Accepts strings where #a = #b. [AB]
(f) Accepts strings where (#a mod 3) = (#b mod 3). [AB]
( Tom 7's page ) |