The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998


Detailed Solutions

Chapter 3, Problem 9, Part 3




The nondeterministic automaton simply guesses which of the 3 symbols will be the one to appear at least 4 times in all and proceeds to verify that. (Since there could be more than 4 appearances, we also let it guess which appearances it wants to count.)
A deterministic automaton is easy enough to build, but will need to keep track of the number of as, of bs, and of cs seen so far, until one of them has been seen 4 times. So we will have states of the type "seen x as, y bs, and z cs," for 0 <= x,y,z <= 3, or at least 43=64 states. The machine must have one more state for accepting and thus will have 65 states in all. Whenever it sees a d, it simply loops in place; whenever it sees one of the three symbols of interest, it moves to the state denoting the updated count, until it reaches the accepting state, which is a trap.