# Find Myhill–Nerode equivalence classes of language $\{0^n1^n: n \in \mathbb{N}_0 \}$

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

$$L = \{0^n1^n: n \in \mathbb{N}_0 \}$$ where $$\mathbb N_0$$ is the set of natural numbers including $$0$$, i.e., $$0, 1, 2, \cdots.$$

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$$ (and vice versa).

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 \mathbb{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 \mathbb{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.

For string $$s$$, call a string $$e$$ an extender of $$s$$ (with respect to $$L$$) if $$es$$ in $$L$$.

$$x$$ and $$y$$ are in the same equivalence class iff (a string is an extender of $$x$$ iff it is an extender of $$y$$).

Let us describe some sets.

• Let $$O_{k}=\{0^k\}, \ \text{ where } k \in \mathbb N_0$$.
For any string $$s$$ in $$O_k$$, string $$e$$ is an extender of $$s$$ iff $$e=0^i1^{i+k}$$ for some $$i\in\mathbb N_0$$.
• Let $$L_{k}=\{0^{m+1+k}1^m1: m\in\mathbb N_0\}, \ \text{ where } k \in \mathbb N_0.$$
For any string $$s$$ in $$L_k$$, string $$e$$ is an extender of $$s$$ iff $$e=1^{k}$$.
• Let $$R=\{x\in\Sigma^*: x\text{ is not in any }O_k\text{ or }L_k\}$$, where $$\Sigma\supseteq\{0,1\}$$ is the alphabet.
Note that any string that can be extended to a string in $$L$$ must be $$0^i1^j$$ for some $$i\ge j\ge0$$, i.e., must be in $$O_k$$ or $$L_k$$ for some $$k$$.
Hence, for any string $$s$$ in $$R$$, there is no extender of $$s$$.

The description above shows that all (Myhill–Nerode) equivalence classes of $$L$$ in $$\Sigma^*$$ are $$O_0,O_1, O_2,\cdots, L_0, L_1, L_2, \cdots$$ and $$R$$.

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 \mathbb{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 means $$O_n$$ defined above, then it does have only one word, $$0^n$$. The unique word in $$O_n$$ is only equivalent to itself.