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


(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]


(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 )