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.