# Prove $\{a^kb^l: 1\leq k\leq l\}$ 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 get that I have infinite number of classes? Can't all $$c$$ belong at the same class for example?

• It looks you did not understand Myhill-Nerode's theorem correctly. To prove $L$ is nonregular, you should find an infinite number of strings such that for any two of them, say $c$ and $d$, there exists a string $z$ such that exactly one of $cz$ and $dz$ is in $L$. In other words, $c$ and $d$ are distinguished by $z$. Commented Jun 15, 2023 at 19:57

The idea is to find infinitely many strings that are distinguishable from each other with respect to the Myhill-Nerode equivalence relation defined by $$L$$.
Consider the strings $$a, a^2, a^3, \cdots$$. Let us check they are distinguishable from each other.
Let $$a^{k_1}$$ and $$a^{k_2}$$ be two of them. WLOG, assume $$k_1.
Then $$a^{k_1}b^{k_1}\in L$$ but $$a^{k_2}b^{k_1}\notin L$$.
That is, $$a^{k_1}$$ and $$a^{k_2}$$ can be distinguished by appending $$b^{k_1}$$ to them. That is, these two strings are distinguishable. That is, these two strings are in different Myhill-Nerode equivalence classes.