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:
- If given the equivalence classes, how can one prove that they are indeed induced from the relation?
- 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.