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

Question

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.

Answer 1

I don't know if there is an easier (more explicit) solution, but the following just-do-it proof works rather well:

Let $\{(x_n, y_n) \mid n \in \Bbb{N}\}$ be an enumeration of all pairs $(x,y)$ of finite length words over $\Sigma = \{0,1\}$ with $x \neq y$. Note that this set is indeed countable (because we are only considering words of finite length), so that there is such an enumeration.

We will now construct two sequences of sets $(G_n)_{n \geq 0}$, $(B_n)_{n \geq 0}$ of (finite length) words over $\Sigma$ and a sequence $(\varepsilon_n)_{n \geq 1}$ of (finite length) words with the following properties:

1. $|G_n| = |B_n| = n$ (i.e. each of these sets contains $n$ elements)
2. $G_n \subset G_{n+1}$ and $B_n \subset B_{n+1}$
3. $G_n \cap B_n = \emptyset$
4. $x_k \cdot \varepsilon_k \in G_n$ and $y_k \cdot \varepsilon_k \in B_n$ for all $1 \leq k \leq n$. (Here, I write $x \cdot y$ for the concatenation of $x$ and $y$).

For $n= 0$, start with $G_0 = B_0 = \emptyset$.

Now, if $G_0, \dots, G_n$ and $B_0, \dots, B_n$ and $\varepsilon_1,\dots, \varepsilon_n$ are already constructed with the above properties, choose some (finite length) word $\varepsilon_{n+1}$ such that $x_{n+1} \cdot \varepsilon_{n+1} \notin G_n \cup B_n$ and $y_{n+1} \cdot \varepsilon_{n+1} \notin G_n \cup B_n$. As $G_n \cup B_n$ is a finite set, one can always find such a word $\varepsilon_{n+1}$.

Set $G_{n+1} := G_n \cup \{x_{n+1} \cdot \varepsilon_{n+1}\}$ and analogously $B_{n+1} := B_n \cup \{y_{n+1} \cdot \varepsilon_{n+1}\}$. Then property (1) and (2) above are clear. Property (3) holds, because $x_{n+1} \neq y_{n+1}$ implies $x_{n+1} \cdot \varepsilon_{n+1} \neq y_{n+1} \cdot \varepsilon_{n+1}$ and property (4) is again obvious.

Now define

$$ L := \bigcup_{n=0}^\infty G_n. $$

To show that $L$ has the desired property, let $x \neq y$ be two finite words. Hence, $(x,y) = (x_n, y_n)$ for some $n \in\Bbb{N}$. By property (3), $x_n \cdot \varepsilon_n \in G_n \subset L$ and $y_n \cdot \varepsilon_n \in B_n$.

Now if we had $y_n \cdot \varepsilon_n \in L$, this would imply $y_n \cdot \varepsilon_n \in G_k$ for some $k$. Using property (2), we can assume $k \geq n$. But we also have $y_n \cdot \varepsilon_n \in B_n \subset B_k$ and hence

$$ y_n \cdot \varepsilon_n \in G_k \cap B_k = \emptyset, $$

a contradiction.

Hence, $x_n \cdot \varepsilon_n \in L$ and $y_n \cdot \varepsilon_n \notin L$, so that $x = x_n \not\sim y_n = y$.