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$
1
  • $\begingroup$ Have you tried proving the opposite? $\endgroup$
    – Raphael
    Commented Mar 20, 2013 at 11:20

1 Answer 1

5
$\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$
2
  • 1
    $\begingroup$ Isn't this close to a duplicate? $\endgroup$
    – Raphael
    Commented Mar 20, 2013 at 11:19
  • $\begingroup$ @Raphael, close yes, but sufficiently different for my taste. $\endgroup$
    – vonbrand
    Commented Mar 20, 2013 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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