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: (a) or That is, the output should equal the C expression c1 || c2 || ... || ci (b) and c1 && c2 && ... && ci (c) xor c1 ^ c2 ^ ... ^ ci 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] Be careful. Does your machine accept FROFROG? (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 )