Show that $A=\{0^m 1^n |\text{ }m\text{ is even or }m > n\}$ has infinitely many equivalence classes to prove non-regularity.

Question

Show that $A=\{0^m 1^n |\text{ }m\text{ is even or }m > n\}$ has infinitely many equivalence classes.

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

Answer 1

I claim that for any $a\neq b$, $0^a\not\equiv 0^b$ via the Myhill-Nerode Equivalence relation.

To see why, observe that if $a$ is even and $b$ is not or vice versa, then the string $z=01^{a+b+1}$ will ensure that either $0^az$ is accepted and $0^bz$ is not, or v.v.

So assume that both $a,b$ are even or odd. Without loss of generality, we can assume that $a,b$ are odd, since we can add a $0$ at the end to both.

Without loss of generality, $a<b$. Then, let $z=1^{a+1}$. Thus, $0^az$ will be accepted, while $0^bz$ will not.