0
$\begingroup$

Can someone help me prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j+3 < k \}$ is not a context free language?

I've tried applying the pumping lemma for CFGs and proving case by case (taking x=uvw, at first v is int $a^+$, then v is in $a^+b^+$ etc.but I'm failing to find a contradiction). Any help is welcomed.\

PS: The suggestion does not solve my problem. I know the technique of applying the pumping lemma for CFG to prome a language is not context free, but I don't know how to use it on this particular language.

$\endgroup$
2
$\begingroup$

Firstly I want to point out that what you want to prove that $L$ is a context free language or CFL not grammar. A CFL can be defined by a CFG, but they are very different things. Anyway, back to your question.

I'm going to give you somewhat informal reasoning, but I think you will be able to formalize it if necessary.

Let us assume that $L$ is in fact a CFL. Then the pumping lemma for CFL's holds for $L$. Let n be the number of the pumping lemma for L.

Consider the word $w = a^nb^{n+1}c^{3n+4} \in L$

From the pumping lemma we have that $w = uxyzv, |xyz| \leq n, |xz| \geq 1, (\forall i \geq 0)[ux^iyz^iv \in L$]

We have two inequalities we can try to break:

  1. $i < j$
  2. $i + 2j + 3 < k$

Assume $xz$ does not contain $c$. This means that $xz$ contains only $a$'s or $b$'s (or both). Since $xz \geq 1$ This means we can pump up the word as much as necessary to break inequality $(2)$ -The right side of the inequality will remain the same when we pump up, but the left side will increase by at least $1$ on each step.

So we have deduced that $xz$ must contain a $c$.

Assume that $xz$ contains only $c$'s. Since $xz \geq 1$ we can pump down to remove at least one $c$. This will again break inequality $(2)$ since the right side will become less than or equal to the left.

So we have deduced that $xz$ must contain both a $b$ and a $c$. But since $xz$ contains a $b$, this means that we can pump down and remove at least one $b$, thus breaking inequality $(1)$.

Thus we have shown that no matter how we break up $w$ we can always pump it out of the language. This is contradiction with out assumption that $L$ is a $CFL$ so it must mean that $L$ is not a $CFL$.

$\endgroup$

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.