# Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

Suppose $\Sigma = \{0,1\}$. Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its equivalence classes is a singleton set; that is, if $x,y \in \Sigma^*$ with $x \neq y$, then $[x] \neq [y]$, where $[x]$ and $[y]$ are equivalence classes with representative elements $x$ and $y$, respectively.

I suspect that this language cannot be regular, since the index of $R_L$ is infinite.

• Deleted my answer and updated the title to emphasize the fact that $\Sigma$ is not a unary alphabet, since this is an important element of the question. Oct 16, 2014 at 22:39
• A quick note; whatever language you find, it definitely won't be regular, as you correctly suspect. I wasn't able to think of one and have to run now. Oct 16, 2014 at 22:45

Consider the language $L$ consisting of words $w a 0 1^n$ where $w$ is an arbitrary word, $a$ is either 0 or 1, $w$ has at least $n$ letters and the $n$-th letter of $w$ is $a$. Clearly, given a word in $L$ there exists exactly one decomposition to this form (define $n$ to be the number of trailing ones in the string).

If $w \neq u$ then without loss of generality $w_i = 0, u_i = 1$ for some $i$. But then $w 0 0 1^i \in L$ while $u 0 0 1^i \notin L$. If $w$ is a prefix of $u$, then you can take $n$ which is larger than the length of $w$ but smaller than length of $u$.

In other words $L=\{v a u a 0 1^n : |v| = n-1, |a| = 1\}$; clearly this is a CFL.

(This is a variant of my answer from Can a language have $\Sigma^{*}$ as its syntactic monoid?)

A random language $L$ satisfies this property almost surely. Indeed, consider any two $x,y \in \Sigma^*$. For every $z \in \Sigma^*$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$, so almost surely $xz \in L \not\Leftrightarrow yz \in L$ for some $z$. That is, any two $x,y \in \Sigma^*$ are inequivalent modulo $L$ almost surely. Since there are only countably many pairs $x,y \in \Sigma^*$, all of them are inequivalent modulo $L$ almost surely.

We can "derandomize" this construction using diagonalization. Let $(x_1,y_1),(x_2,y_2),\ldots$ be some enumeration of all pairs of different words in $\Sigma^*$. We define sets of words $A_n,B_n$ inductively; for each $n$, $A_n$ and $B_n$ will be disjoint finite sets, and $A_n \supseteq A_{n-1}$, $B_n \supseteq B_{n-1}$. The base case is $A_0 = B_0 = \emptyset$. Given $A_{n-1},B_{n-1}$, let $w$ be some word such that $x_nw \notin B_{n-1}$ and $y_nw \notin A_{n-1}$, and define $A_n = A_{n-1} \cup \{x_nw\}$ and $B_n = B_{n-1} \cup \{y_nw\}$; such a word $w$ exists since $A_{n-1},B_{n-1}$ are finite. Let $A = \bigcup_{n \geq 0} A_n$ and $B = \bigcup_{n \geq 0} B_n$, and note that $A,B$ are disjoint. The language $L = A$ separates every pair of words.

The language of palindromes over a non-unary alphabet is a nice example. See for example this question.