Prove any DFA with $k<2^n$ states does not accept the strings with an odd number of some character.

Question

Let the language $L_n$ have character set $\Sigma=\{a_1, ..., a_n\}$. $L_n$ has exactly those words which contain some character an odd number of times. That is to say, $\forall w\in L_n\exists a\in \Sigma$ such that $a$ occurs in $w$ an odd number of times. Equivalently if $L_n^i$ is the language with each word containing an odd number of $a_i$ then $L_n = L_n^1\cup ...\cup L_n^n$.

I have already produced an NFA that accepts $L_n$ and a DFA of $2^n$ states which does as well.

I now need to prove that this is the smallest DFA accepting this language. I am given the hint to suppose that there is a DFA of $k<2^n$ states which accepts $L_n$, and then show that there are some strings $u,v\in \Sigma^*$ where $u$ contains $a$ and odd number of times, $v$ contains it an even number of times, and the DFA must terminate on both at the same state.

I've been trying to take the $2^n$ as a strong hint, like maybe consider all strings of length $n$, but there are $n^n$ of these. Maybe consider all strings of length $n$ using only characters $a,b$. Since there are $k<2^n$ states, then some two strings like this must be sent to the same state. The rejected strings in this set are those with even numbers of $a$ and $b$ but I have no way of knowing if two such instances of these go to the same state, or if they did, how that would even matter.

Maybe consider all choices of strings where $a_1$ occurs either once or 0 times, and $a_2$ occurs once or 0 times, etc. There are $2^n$ choices of these so some 2 of these must go to the same state. The only string not in the language here is the empty string. Still I'm stuck.

Answer 1

Let $A = \{a_1, \ldots, a_n\}$ be the alphabet. You can use the fact that the states of the minimal DFA of $L$ can be identified with the left quotients $$ u^{-1}L = \{v \in A^* \mid uv \in L\} $$ where $u$ ranges over $A^*$. Now, for $k_1, \ldots, k_n \in \{0,1\}$, consider the languages $$ L(k_1, \ldots, k_n) = \{ u \in A^* \mid |u|_{a_1} \equiv k_1 \bmod 2,\ \dotsm\ , |u|_{a_n} \equiv k_n \bmod 2\} $$ These $2^n$ languages are clearly distinct (and even pairwise disjoint) and I let you verify that all of them are of the form $u^{-1}L$ for some $L$. Therefore, the minimal DFA of $L$ has at least $2^n$ states (and actually exactly $2^n$ states, as you have shown).