# Use of Myhill-Nerode Theorem to prove minimal number of states

I'm confused about how we can use the Myhill-Nerode Theorem to solve this problem, some pointers would be very helpful

Let $Σ = {\{a, b}\}$ and $C_k=Σ^*aΣ^{k-1}$

Prove that for each k, no DFA can recognize $C_k$ with fewer than $2^k$ states.

## 2 Answers

You need to find $2^k$ words which belong to different equivalence classes of the Myhill–Nerode relation. Put differently, you need to find a collection of $2^k$ words such that for any two of them $x \neq y$ there is a word $z$ such that $xz \in L$ and $yz \notin L$ or vice versa.

(I know, ancient question)

Consider the $$2^k$$ different strings in $$\Sigma^*$$ of length $$k$$, and consider which of those strings are equivalent to which other of those strings under the equivalence relation used in the Myhill-Nerode theorem.

Obviously, strings that end in a aren't equivalent to strings which end in b because if you attach a suffix of length $$k-1$$, the strings that end in a are in $$C_k$$ but the strings that end in b aren't.

Similarly, strings with the second-to-last letter of a aren't equivalent to strings with the second-to-last letter b because of what happens with a suffix of length $$k-2$$, and so on.

Therefore none of these strings are equivalent to each other, and we're done.