Given a constant $k$ we will define the language: $$L_k =\{x\#y \mid x \in \{0,1\}^k, y \in \{0,1\}^* \text{ and } x \not=y\}$$ How many Nerode equivalent class does $L_k$ have?
I need to show the most tight bounds I can find.
Can anyone give me a clue?
Thanks
[Note for those unfamiliar with the term: Nerode equivalence is defined as $s_1Rs_2$ if and only if $\forall t\in \Sigma^* s_1t\in L \iff s_2t\in L$.]