Skip to main content
5 of 8
added 15 characters in body

Prove a language is not regular using Myhill-Nerode theorem

I have searched quite a few posts here so that I can prove that the language $L=\{a^kb^l: 1\leq k\leq l\}$ is not regular (using Myhill-Nerode's theorem). I know that I must find an infinite number of pairs $(c,d)$ such that if $R$ is the equivalence relation defined by Myhill-Nerode's theorem, there is a string $z \in \{a,b\}^*$ s.t. if $cRd \Rightarrow \neg (cz R dz)$

I tried $c=a^{n+3}b^n$ and $d=a^{n+1}b^n$, using $z=b^2$.

What troubles me is: I can't assume that $c R d$ since it might not be holding like in this answer. However if I chose $c, d\in L$ I can't find a string $z$. What could I do?

And if I find $c,d$ how do I know that all c are not equivalent and all $d$ are not equivalent, and hence I only have finite number of classes?