im having some problems when it comes to Pumping Lemma of Context-free Language ... this is the Language :

$$L = \{a^n b^n c^m | n\ge 0 , 0 \le m \le 2n \}$$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $p,r>0$ be the pumping length given by the lemma.

Let $z=a^p b^p c^r$, then $z∈L$

Than according to the lemma, z can be written as z=uvwxy where the following properties hold:

$$|vx|≥1$$ $$|vwx|≤n$$ for every $i≥0$, $uv^iwx^iy∈L$

for the cases $i$ always had some problems ... there is one ..

$vx = a^n b^n$ (no $c$'s )

i really have some problems understanding the PL for CF Language

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Dec 18 '16 at 21:28
  • $\begingroup$ Your question is a very basic one. Let me direct you towards our reference questions which cover some fundamentals you seem to be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck! $\endgroup$ – Raphael Dec 18 '16 at 21:29
  • 2
    $\begingroup$ What is the question here? $\endgroup$ – Raphael Dec 18 '16 at 21:29
  • $\begingroup$ Try $m=2n$ and pumping down. $\endgroup$ – Yuval Filmus Feb 18 '17 at 14:17

The solution which I provide below is very similar to Example 2.37 in classical Sipser's book "Introduction to the theory of computation"

Let $p,r>0$ be the pumping length given by the lemma.

I think you have a little abuse of notation. Look carefully at definition. It states that if $L$ is $CFL$ then, there exists some constant $p$ (pumping length) that for every string $s \in L$ such that $|s| \ge p$, $s$ can be divided on five parts such that the following properites hold:

$|vx|≥1$ $|vwx|≤n$ and for every $i≥0, uv^iwx^iy∈L$

So, let us take $s = a^nb^nc^{2n}$, where $n+n+2n > p$. Then the conditions for lemma are hold, and it follows that $s = uvwxy$ with all those properties. From the first property we get that at least one of $v$ or $x$ is non-empty string. Now, we should consider several cases:

1) At least one of $v$ or $x$ contains diffent letters of the alphabet (for example, $v$ = $zabt$, $|z|, |t| \ge 0$). Then $uv^2wx^2y$ doesn't has the form $a^nb^nc^m$ (problems with order, in my example $v^2 = zabtzabt$), so we get a contradiction.

2) Either $v$ or $x$ contains only one letter from alphabet. Here we get such cases:

2.1) $v$ and $x$ don't contain the letter $c$. By lemma the string $s_1 = uv^0wx^0y \in L$. But $s_1$ has less than $n$ letters $a$ or $b$, while it contains $2n$ letters $c$. So, the property $m \le 2n$ doesn't hold in this case and we get a contradiction.

2.2) $v$ or $x$ contain the letter $c$, so either $a$ or $b$ doesn't belong to $v$ and $x$. Then string $s_1 = uv^2wx^2y$ contains at least $2n + 1$ $c$'s, and only $n$ $a$'s or $b$'s. Again, we get a contradiction.

  • 1
    $\begingroup$ Welcome! Please note that we have a set of reference questions that provide well-vetted explanations and examples for common exercise problems such as in this question. You may want to invest your time on more original questions. $\endgroup$ – Raphael Dec 18 '16 at 21:30

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