Challenge: Let's consider the generalization of the language given in the question above. Let $L$ be the set of all binary strings that contain a $1$ as the $n-$th symbol from the end of the string. Prove why a DFA to accept L must have at least $2^n$ states.