Construct a NFA whose language is the set of strings over {a,b,c,d} which do not contain all four symbols. Of course, by keeping track of which symbols we have seen so far, we can construct a DFA for this language using 2^4 = 16 states. Your solution should have at most 8 states, which will force you to exploit nondeterminism.