How to characterize equivalence classes induced by Myhill-Nerode theorem?

Question

Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N_0(w)=N_1(w) \rbrace$, where $N_0(\cdot)$ and $N_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes induced by the relation on $\{0,1\}^\ast$ $$x \thicksim_{L} y \iff \forall z\in \{0,1\}^\ast \left(xz \in L \iff yz \in L\right)$$ The reference I have already shows that the (obviously, infinitely many) classes are of the form $C_k=\lbrace w\in \lbrace 0,1 \rbrace ^{\ast} : N_0(w)-N_1(w)=k \rbrace $ and clearly $\bigcup_{k\in\Bbb Z } C_k = \{0,1\}^\ast $, but I have no idea how could I have deduced this correct characterization myself.

When given a regular language, I find it easier to construct a suitable minimal DFA and then "back engineer" each state to a useful characterization of its class. But for a non-regular language, I'm having a really hard time working with the relation definition. In this particular example, I don't understand how it applies to the classes $C_k$ above.

So for me there are two underlying questions here:

1. If given the equivalence classes, how can one prove that they are indeed induced from the relation?
2. However, if they are not given, is there a systematic\algorithmic approach to characterize all of these classes for a given language? mainly, a non-regular one.

Answer 1

To prove that the classes $C_k$ are equivalence classes for the Myhill-Nerode relation we need to show

1. For any strings $x,y \in C_k$ there does not exist a distinguishing extension of $x$ and $y$. This proves $C_k \subseteq [w]$.
2. For any $x \in C_j$ and $y \in C_k$ there does exist a distinguishing extension. Since every string $\omega$ belongs to some $C_k$ this shows that the $C_k$ form a partition of $\Sigma^*$.

These together show that the $C_k$ are exactly the equivalence classes under $\sim_L$.

Let $N(w)$ denote $N_0(x) - N_1(x)$.

---

For the first part, note that $x, y \in C_k \implies N(x) = N(y)$. Then for any extension $r$, we have that

$N(xr) = N(x) + N(r) = N(y) + N(r) = N(yr)$

and so $xr \in L \iff yr\in L$. Thus $r$ cannot distinguish $x$ and $y$.

---

For the second part, we have that $N(x) \neq N(y)$. Assume WLOG $N(x) > 0$.

Then the extension $1^{N(x)}$ distinguishes $x$ and $y$ since $$N(x1^{N(x)}) = N(x) - N(x) = 0 \implies x1^{N(x)} \in L$$ while $$N(y1^{N(x)}) = N(y) - N(x) \neq 0 \implies y1^{N(x)} \notin L$$

---

Intuitively, we interpret the equivalence classes as "states" of some machine for deciding the language. This is literally true in the case of regular $L$, but even in this infinite case we can interpret "state" to mean $k$. Once two strings are in the same state, there is no going back: there is no further information that we can feed to the machine and cause it to diverge.

In this particular case, we look at the definition of the language and note that the only information that we care about is $N(w)$. Since this information in some sense captures all we need to know about a string, it makes sense that strings that are identical under this classification can never be distinguished by the language.

There is certainly no algorithmic way of classifying $\sim_L$ in full generality since even deciding whether two strings belong to the same class is undecidable clearly for undecidable languages $L$.

In the restricted case of context free languages I don't know of any generic canonical characterization. There are some relevant discussions here and here