Show that $A=\{0^k 1^m 0^n |\text{ }n=k+m\}$ has infinitely many equivalence classes.

Question

Show that $A=\{0^k 1^m 0^n |\text{ }n=k+m\}$ has infinitely many equivalence classes.

I'm trying to prove that $A$ is a non-regular language. Alternatively, I could use closure properties - but have been struggling.

Answer 1

Consider the string $S_k = 0^k$. Consider the string $T_k = 1^k$.

Note that for all positive integers $j, k$, we have $S_k T_j \in A$ iff $k = j$.

Therefore, each $S_k$ is in a different equivalence class (since if $k \neq j$, then $S_k T_k \in A$ but $S_j T_k \notin A$).

But a regular language can only have finitely many equivalence classes. So $A$ is not a regular language.