1
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I understand the hint to refer not to string length but to the intuitive idea that any recognizer must keep track of the parity of how many instances of each letter $a\in\Sigma$ it has seen so far. There are $n$ such parities, so $2^n$ combos of parity values to keep track of. And so on. $\endgroup$ – kimchi lover Sep 23 '17 at 16:47
  • $\begingroup$ @kimchilover Ahh, shit, got it. Never even occurred to me to think in those terms, but it makes good sense. $\endgroup$ – Addem Sep 23 '17 at 16:52
2
$\begingroup$

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).

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.