1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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<m\} \end{aligned} $$

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$.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Oct 17 '18 at 15:39
  • $\begingroup$ Good catch! Each of those $0^k$ should be in their own classes. $\endgroup$ – Apass.Jack Oct 17 '18 at 15:49

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.