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.

  • $\begingroup$ I think that the equivalence classes of the syntactical correspond exactly to the reachable states of a minimized DFA. So if you are able to construct some automaton, you could determinize and minimize it and kind of "read" the classes from there. Your relation takes only the left context, sou your equivalence classes should be unions of classes of the syntactical congruence. This would be an almost mechanic approach, but maybe not a very efficient one. $\endgroup$ – Peter Leupold Dec 1 '18 at 18:15

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.