Understanding proof that no DFA can recognize L with fewer than 2^k states

Question

Let Σ = {a, b} and L = {ww | w ∈ Σ∗ and w is of length k}. Show that for each k, no DFA can recognize L with fewer than 2^k states.

What I understand is that we prove this by contradiction. Assume that L has less than 2^k states i.e L has 2^k -1 states. We then use the pigeonhole principle which would mean that two of these strings would have to be in the same state meaning that if we append a new string to both of these strings that are currently in the same state, these new strings should either both be accepted or rejected. This is where we want the contradiction. But the question is how to prove this mathematically?

If we take Wi and Wj two distinguishable string which ends at the same state q then after adding some string X, both WiX and WjX should end at the same state. But how can I prove that both does not end at the same state to get the contradiction?

Answer 1

Alternatively, you can use Myhill–Nerode theorem.

For each $x, y \in \Sigma^k$, $x \ne y$, we have $x \not \sim_L y$ because $xx \in L$ but $yx \notin L$. Therefore, we have $|Q(M)| \ge |\Sigma^\ast/{\sim_L}| \ge |\Sigma|^k = 2^k$ for a DFA $M$.

Answer 2

You need to be more specific about what $2^k$ strings you are applying the pigeonhole principle to. This proof will not work with arbitrary strings e.g. in the case $k=4$, we have that $W_i=aab$ and $W_j=abb$ are different but neither is the prefix of a word in $\mathcal L$, so they might as well take you to the same state (one where no accepting state is reachable).

I take it that there are also restrictions on $k$ (it must be even), because in the case $k=3$ we have that $\mathcal L=\emptyset$ and $\emptyset$ can be recognised by a DFA with one state (a non-accepting state with a self-loop).

At some point you may need to bear in mind that $W_i$ and $W_j$ could be of different lengths.

Answer 3

So the answer is according to pigeonhole principle, two different strings end at the same state. Let say Wi and Wj end at the same state(say q). Since DFA don't have memory and only depend on the current state( and not on how the current state was reached), M will give the same answer(either accept or reject) on string WiU and WjU no matter what U is(where U is any string). Now if we find a string U such that WiU ∈ L and WjU ∉ L or vice versa then M gives the same answer(either both accept or reject) resulting in contradiction and proving M does not recognize L with fewer than %2^k% states