0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Parth Patel Mar 10 at 6:42
  • $\begingroup$ My edit is rejected. Don't know why. Hope you got what I am trying to convey. $\endgroup$ – Parth Patel Mar 10 at 6:43
  • 1
    $\begingroup$ Fixed. Sorry for the little lapse. $\endgroup$ – Peter Leupold Mar 10 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.