How many Nerode equivalence classes does the language $x\neq y$ have?

Question

I have a language $L_k$ over the alphabet $\Sigma=\{0,1,\#\}$ defined as follows: \begin{equation} L_k=\{x\#y|x\in\{0,1\}^k,y\in \{0,1\}^*\wedge x\neq y\} \end{equation}

I would like to find all the Nerode equivalence classes for this language. Since this definition is somewhat hard to google I'm including it here.

The Nerode equivalence $R_L$ on a language $L$ over an alphabet $\Sigma$ is defined as follows. For $s_1,s_2\in \Sigma^*$ $s_1R_L s_2$ if and only if $\forall t\in\Sigma^* s_1t\in L\iff s_2t\in L$.

If we have $s_1\in\Sigma^h$ where $0<h\leq k$ such an $s_1$ must be in it's own class. We can show this by contradiction in parts. Suppose $s_2\in\Sigma^*$ and $s_2\neq s_1$.

Case 1) $|s_2|\neq |s_1|$

Choose $t=0^{h-k}\#$ then $s_1t=s_10^{h-k}\# \in L_k$ but $s_2t=s_20^{h-k}\#r\not\in L_k$ since $s_2t$ has a $\#$ somewhere other than at the $k+1$'st position.

Case 2) $|s_2|=|s_1|=h$

Define $t=0^{h-k}\#s_10^{h-k}$. Then $s_1t=s_10^{h-k}\#s_10^{h-k}\not \in L_k$ since the sides around the $\#$ are equal, but $s_2t=s_20^{h-k}\#s_10^{h-k} \in L_k$ since $s_1\neq s_2$ and so the padding stays unequal.

Now how do I proceed for $s_1$ longer than $k$? Any hints or help appreciated.

Answer 1

The equivalence classes are as follows:

• Class $B$: All words with (1) $\#$ not on position $k+1$, (2) $\#$ missing from position $k+1$, (3) more than $2k+1$ letters, or of the form (4) $x\#x$, where $|x|=k$.
• Class $G_\ell$ for $1 \leq \ell \leq k$: All words of the form $x\#y$, where $|x|=k$, $|y| = \ell$, and $x_i \neq y_i$ for some $i \leq \ell$.
• Every other word is its own equivalence class. These are words of the form $x$ for $|x| \leq k$ and words of the form $x \# y$, where $|x| = k$, $|y| < k$, and $y$ is a prefix of $x$ (possibly $y = \epsilon$).

All words in $B$ and all of their extensions are not in $L_k$. In contrast, all other words extend to a word in $L_k$. This shows that $B$ is an equivalence class. All words in $G_\ell$ can be extended to a word in $L_k$ by any string of length exactly $k-\ell$. In contrast, words of the singleton classes don't have these properties. This shows that the $G_\ell$ are equivalence classes.

Finally, to show that the singletons are equivalence classes, it suffices to consider two words of the same length and show that they can be extended so that one of them is in $L_k$ and the other aren't. There are a few cases to consider, but they are all pretty simple. One also needs to check that the equivalence classes together cover all words.