Design NFA with changing alphabet and language

Question

I ran into this exercise and i thought about it for a few hours and got to nothing.

our alphabet is {1...n} and our language Ln contains all the words under Σ* so that each word in the language doesn't contain at least one letter from the alphabet.

• for example: if n=5, the word w={111223432} is in the language because '5' is missing in the word. the word w={1352224} is not in the language because all the letters 1...n are in the word.

I need to design an NFA for this language that has n+1 states.

Again, I tried a few things and don't exactly have a good idea.

Answer 1

For simplicity, let's do this for the alphabet {a, b, c}. Imagine that you have a string in your language. That means that it's missing a, or it's missing b, or it's missing c (inclusive or). If we knew which character was missing, it would be really easy to check whether a string never had a copy of that character using a single-state NFA consisting of an accepting state that transitions back to itself on everything except that character.

Since there are only finitely many characters in the alphabet, we can build three one-state NFAs, each of which are designed to check whether a string is missing a particular character.

To build the overall machine, have the start state of the NFA nondeterministically guess which character is missing by adding ε-transitions from the start state to each of the individual one-state NFAs we built earlier. You now have a four-state NFA for this language. (You can see a picture of it here.) Hopefully it's not too hard to see how to generalize this up to larger alphabet sizes!