2
$\begingroup$

$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $

Is this language a context free language? If yes give a PDA. If no, give a proof.

The pumping lemma for context free languages doesn't seem to work here.

Let $p>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$.

For any string of the form $a^ib^j \ s.t.$:

  1. $ j\lt i-1$ choose $v=a, \ x=\epsilon, \ y=\epsilon$

  2. $ j\gt 2i+1$ choose $v=\epsilon, \ x=\epsilon, \ y=b$

  3. $ j = i-1$ choose $v=a, \ x=\epsilon, \ y=b$

  4. $ j = 2i+1$ choose $v=a, \ x=\epsilon, \ y=b$

  5. $ j\gt i,\ j\lt 2i $ choose $v=a, \ x=\epsilon, \ y=b$

$\endgroup$
  • $\begingroup$ Have you tried proving the opposite? $\endgroup$ – Raphael Mar 20 '13 at 11:20
4
$\begingroup$

It is context Free.

You can see it as a union of two languages: $L_1$ where $j>2i$ and $L_2$ which is very similar to the one of this question.

More information you can find in this question.

$\endgroup$
  • 1
    $\begingroup$ Isn't this close to a duplicate? $\endgroup$ – Raphael Mar 20 '13 at 11:19
  • $\begingroup$ @Raphael, close yes, but sufficiently different for my taste. $\endgroup$ – vonbrand Mar 20 '13 at 13:32

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.