# Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$

I'm asked to find all equivalence classes of the language

$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$

We have the following definition:

$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$$

As I understand, words $$x$$ and $$y$$ belongs to different equivalence classes if $$\exists z \in \Sigma^*: xz \in L$$ and $$yz \notin L$$ (or viceversa).

The language L above is not regular so it has infinitely many equivalence classes under $$R_L$$. In order to differentiate between two classes, I was thinking about defining the equivalence relation in the following way:

$$xR_Ly = \text{"}x[n] = y[n] = 0\text{ and }x[n+1] = y[n+1] = 1\text{"}$$

with $$x[k]$$ I mean the $$k$$-th letter in $$x$$. Under this "approach", all equivalence classes are generated by taking $$n$$ to be any number $$\in \mathrm{N}_0$$.

Under my attempt I have the following questions:

In the definition, nothing is said about $$x$$ and $$y$$ in $$(xR_Ly)$$. Do I have to assume that those are two arbitrary words that are already in $$L$$? (If not, then my approach doesn't work).

For a fixed $$n \in \mathrm{N}_0$$ I think $$\exists$$ just one word in the class $$C_n$$. Then does it mean that the unique word in $$C_n$$ is only equivalent to itself?

I think I'm not even close to the answer, so would appreciate any help with this.

Let $$\Sigma=\{0,1\}$$. Here are all (Myhill–Nerode) equivalence classes, $$O_0,O_1, O_2,\cdots, L_0, L_1, L_2, \cdots$$ as well as $$R$$.

\begin{aligned} O_{k} &= \{0^k\}, \ \text{ where } k \in \mathrm{N_0}. \\ L_{k} &= \{0^{m+k}1^m: m \in \mathrm{N} \}, \ \text{ where } k \in \mathrm{N_0}. \\ R &=\{x10^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n\ge m\}\cup\{x0^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n

If $$a\in O_{k}$$ and $$b\in O_{t}$$, $$k\neq t$$, $$a1^{k}\in L$$ while $$b1^{k}\not\in L$$. So $$a$$ and $$b$$ are in different classes.
If $$a\in O_{k}$$ and $$b\in L_{t}$$, $$a01^{k+1}\in L$$ while $$b01^{k+1}\not\in L$$. So $$a$$ and $$b$$ are in different classes.
If $$a\in O_{k}$$ and $$b\in R$$, $$a1^{k}\in L$$ while $$b1^{k}\not\in L$$. So $$a$$ and $$b$$ are in different classes.

If $$a\in L_{k}$$ and $$b\in L_{t}$$, $$k\neq t$$, $$a1^{k}\in L$$ while $$b1^{k}\not\in L$$. So $$a$$ and $$b$$ are in different classes.
If $$a\in L_k$$ and $$b\in R$$, $$a1^k\in L$$ while $$b1^k\not\in L$$. So $$a$$ and $$b$$ are in different classes.

What remain to be proved are the following.

• For any $$k\ge0$$, all elements in $$O_k$$ belong to the same class, which is true trivially since there is only one element.
• For any $$k\ge0$$, all elements in $$L_k$$ belong to the same class.
• all elements in $$R$$ belong to the same class.
• $$\cup_{k=0}^\infty L_k\cup R =\Sigma^*.$$

I will let interested readers to fill in the details.

Now that the correct equivalence classes are shown, let me get to your questions.

In the definition, nothing is said about $$x$$ and $$y$$ in $$(xR_Ly)$$. Do I have to assume that those are two arbitrary words that are already in $$L$$? (If not, then my approach doesn't work)

No, $$x$$ and $$y$$ may or may not be in $$L$$. Your approach doesn't work.

For a fixed $$n \in \mathrm{N}_0$$ I think $$\exists$$ just one word in the class $$C_n$$. Then does it mean that the unique word in $$C_n$$ is only equivalent to itself?

I cannot find where $$C_n$$ is defined. If it is what I guess it is, there are more than one word in $$C_n$$. If it means $$O_n$$ I defined above, then it does have only one word, $$0^n$$.

• The words $0^k$ and $0^{k+1}1$, both in your $L_k$, are not equivalent: $0^k01^{k+1} \in L$ whereas $0^{k+1}101^{k+1} \notin L$. – Yuval Filmus Oct 17 '18 at 15:39
• Good catch! Each of those $0^k$ should be in their own classes. – Apass.Jack Oct 17 '18 at 15:49