Problem : Smaller NFA
In this problem we'll see a very clear example of how NFAs can be built to recognize a language using much fewer states than a DFA would. Consider the following language L: 'Strings of a's, b's, and c's, that do NOT contain at least one of those 3 letters.'
So for example, accca would be accepted, because it does not contain b, as would bbc which does not contain any a's, and bb winch does not contain any a's or c's, but caba would be rejected because it contains all 3 letters of the alphabet in it.
Build a DFA with at most 8 states that recognizes L.
Build an NFA with at most 4 states that recognizes L.
If instead of 3 letters, your alphabet had k letters, and you build a DFA and an NFA for the language the same way you built them in parts a and b, how many states would the DFA have? How' many states would the NFA have?