1
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.