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] 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] ( Answers ) ( Tom 7's Page ) |