Why do non regular languages have infinitely many equivalence classes?

488 Views Asked by At

Let's say I have a language L = {a^nb^m|n != m},

The Myhill-Nerode relation $\equiv_L$ of $L$ is a relation on $\Sigma^*$. It is for words $x,y \in \Sigma^*$ defined by $$ x \equiv_L y \iff \forall z \in \Sigma^*: xz \in L \Leftrightarrow yz \in L $$

why does it have infinitely many equivalence classes ≡L? How do I show/see that?

1

There are 1 best solutions below

10
On BEST ANSWER

HINT: For each $n$ let $w_n=a^nb$, and show that $n\ne m$, then $w_n\not\equiv_L w_m$.