Construct a NFA (nondeterministic finite machine) 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 24 = 16 states. Your solution should have at most 8 states, which will force you to exploit nondeterminism.