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

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.

Consider the language $${C_k}$$, and let $$\sim_{C_k}\subseteq \Sigma\times \Sigma$$ denote the Myhill-Nerode equivalence relation w.r.t to $$C_k$$. As the number of Myhill-Nerode equivalence classes bounds from below the size of the minimal DFA that recognizes $$C_k$$, it is sufficient to bound the number of Myhill-Nerode equivalnce classes from below. Specifically, we show that the relation $$\sim_{C_k}$$ has at least $$2^k$$ equivalence classes. Consider all words $$w_1, w_2, \ldots, w_{2^k} \in \Sigma^k$$, thus, every word $$w_i$$ is of length $$k$$ and consists only of letters from $$\Sigma = \{ a, b\}$$. We claim that for all $$1 \leq i < j \leq 2^k$$, it holds that $$[w_i]_{\sim_{C_k}} \neq [w_j]_{\sim_{C_k}}$$ ($$w_i$$ and $$w_j$$ are not in the same equivalence class) , and hence there are at least $$2^k$$ equivalence classes:

As the words $$w_i$$ and $$w_j$$ are of length $$k$$, we can write them as $$w_i = c_1\cdot c_2 \cdots c_{k}, w_j = d_1\cdot d_2 \cdots d_{k}$$, where $$c_l, d_l \in \Sigma$$ for all $$l\in [k]$$. Recall that the words $$w_i$$ and $$w_j$$ are distinct, and let $$l \leq k$$ be the maximal index such that $$c_l\neq d_l$$. Assume w.l.o.g that $$c_l = a$$ and $$d_l = b$$. Then, any word $$z$$ of length $$l-1$$ is such that $$w_i \cdot z = c_1\cdot c_2 \cdots c_l \cdot c_{l+1} \cdots c_{k} \cdot z$$ has $$c_l =a$$ as its $$k$$'th letter from the end, and $$w_j \cdot z = d_1\cdot d_2 \cdots d_l \cdot d_{l+1} \cdots d_{k} \cdot z$$ has $$d_l = b$$ as its $$k$$'th letter from the end. Hence, every word $$z$$ of length $$l-1$$ is such that $$w_i \cdot z \in C_k$$, but $$w_j\cdot z \notin C_k$$, and thus $$[w_i]_{\sim_{C_k}} \neq [w_j]_{\sim_{C_k}}$$.