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

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.

## 1 Answer

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 is not regular via the pumping lemma.

• Your idea is correct but there is little mistake . I am not able to edit properly. Please update it to a^p b^(p-1) as i>j,not i>=j. Thanks. – Parth Patel Mar 10 at 6:42
• My edit is rejected. Don't know why. Hope you got what I am trying to convey. – Parth Patel Mar 10 at 6:43
• Fixed. Sorry for the little lapse. – Peter Leupold Mar 10 at 6:46