Pumping lemma L={$a^i$ $b^j$, / 0<j<i<infinity}?

Question

How to prove that above language is not regular. I tried using pumping lemma but am not able to prove and what to select as initial string. I also searched for other answers but this question is not discussed. Please help me. Thanks.

Answer 1

This is a bit tricky, because pumping in the initial block of $a$ will not violate the definition of the language, EXCEPT for one case: let $p$ be the constant from the pumping lemma and take the string $a^pb^{p-1}$. The pumping takes place in the initial block of $a$, because $|xy|<=p$. Now note that the lemma says, that also $xy^0z$ must be in the language. In our case $y^0$ means the deletion of some letters $a$, and therefore the resulting word is not in $L$.

Alternatively, you could use the fact that the regular languages are closed under reversal. It should be straight-forward to prove that $\{b^ja^i: 0<j<i \}$ is not regular via the pumping lemma.