1
$\begingroup$

This is the Pumping Lemma for Context Free Languages I refer:

For all context free languages $L$ there exists some $k \in \mathbb{N} \mid \forall z \in L$ with $\left | z \right | \ge k$, there exist $uvwxy$ such that:

  1. $z= uvwxy$,
  2. $v$ and $x$ are not both $\epsilon$,
  3. $\left | vwx \right | \le k$, and
  4. $\forall i, uv^iwx^iy \in L$

And this is the exercise I encounter some problems:

$L = \left \{ a^nb^mc^n \mid m \ge n \right \}$ is not context free.

  1. Proof by contradiction using the pumping lemma for context-free languages. Assume that $L$ is context free, so the pumping lemma holds for $L$. Let $k$ be as given by the pumping lemma.

  2. Choose $z = a^kb^kc^k$. Now $z \in L$ and $|z| \ge k$ as required.

  3. Let $u, v, w, x, y$ be as given by the pumping lemma, so that $uvwxy = a^kb^kc^k$, $v$ and $x$ are NOT both $\epsilon$, $|vwx| \le k$ , and for all $i$, $uv^iwx^iy \in L$.

  4. If either $v$ or $x$ contains more than one kind of symbol, we can pump with $i = 2$; then the string $uv^2wx^2y \notin L$ (and not even in $L(a^*b^*c^*)$). If $v$ and $x$ contain at most one kind of symbol each, then we can pump with $i = 0$. The substrings $v$ and $x$ fall within the string $a^kb^kc^k$ in one of these ways:

Lang_a^nb^mc^n_m-ge-n_ncfl.png

Because $v$ and $x$ are not both $\epsilon$, $uv^0wx^0y$ :

case 1 : has fewer $a$s than $c$s.
case 2 : there are either fewer $a$s than $c$s, or fewer $b$s than $c$s, or BOTH.
case 3 : there are fewer $b$s than $a$s and $c$s.
case 4 : there are fewer $c$s than $a$s, or fewer $b$s than $a$s, or BOTH.
case 5 : there are fewer $c$s than $a$s.
case 6 : contradicts $|vwx| \le k$.

  1. Thus, all cases contradict the pumping lemma. By contradiction, $L = \left \{ a^nb^mc^n \mid m \ge n \right \}$ is not context free.

So my questions are:

Looking at the case 2:

case 2 : there are either fewer $a$s than $c$s, or fewer $b$s than $c$s, or BOTH.

What is the meaning of that -fewer-, and -BOTH-?

Since we are considerng the string $uv^0wx^0y$: if I understand, $v$ contains ALL the $a$s and $x$ contains ALL $b$s, so if we have $v^0$ it means that $v$ contains ZERO $a$s, and $x^0$ it means that $x$ contains ZERO $b$, but, why it is stated -fewer- $a$, $b$ instead of saying plainly ZERO?

And also if the pumping lemma clearly say that $v$ and $x$ can't be both $\epsilon$. What is the meaning of that -BOTH- in case 2? If I understand, if that -fewer- means ZERO, follows that there are both zero $a$s and zero $b$s, but, against what said in the lemma.

Please, can you explain me better? Many thanks!

$\endgroup$
1
+50
$\begingroup$

You're looking at the case where $$a^k b^k c^k = uvwxy$$ and where $v$ consists of just $a$'s, and $x$ consists of just $b$'s. The claim is that pumping fails with $i = 0$, i.e., that $uwy \not \in L$.

This is so, because at least one of the following two things happens:

  • $uwy$ contains fewer $a$'s than $c$'s (this is the case if $v$ is not $\epsilon$);
  • $uwy$ contains fewer $b$'s than $c$'s (this is the case if $x$ is not $\epsilon$).

At least one of those things happens because $v$ and $x$ are not both $\epsilon$ (and it is possible that both things happen, namely if $v$ and $x$ are both not $\epsilon$, which is the reason for the "or both" statement).

Note, by the way that $v$ does not (necessarily) contains all the $a$'s: some of them might be in $u$ or $w$. Similarly, $x$ does not necessarily contain all the $b$'s: some of them might be in $w$ or $y$.

$\endgroup$
  • $\begingroup$ sorry, it's not clear: if there are fewer $a$'s than $c$'s, does $v$ would be equal to $\epsilon$? $\endgroup$ – JB-Franco Apr 12 '17 at 21:06
  • $\begingroup$ and also, you say, in the first happening, that $v$ is not $\epsilon$, and before it you write $uwy$, where here is $v^0 = \epsilon$. Can you explain me better? $\endgroup$ – JB-Franco Apr 12 '17 at 21:16
  • 1
    $\begingroup$ in the first case, where $v$ is not $\epsilon$, say $v = a^l$. Then $uwy$ contains $k - l$ $a$'s and $k$ $c$'s, i.e., fewer $a$'s than $c$'s. The point is that if $v$ is not $\epsilon$, then $uwy$ contains fewer $a$'s than $uvwxy$ does, because you removed all the $a$'s that are in $v$. $\endgroup$ – Magdiragdag Apr 13 '17 at 7:02
  • $\begingroup$ For you second question, $v^0$ is always $\epsilon$, by definition, whatever $v$ is. $\endgroup$ – Magdiragdag Apr 13 '17 at 7:08
  • $\begingroup$ I think my error was to relate $v = \epsilon$, with $v^0$, the first is referred to the content of $v$, that may contain zero symbols, the second is referred only to the pumping, i.e. applying $v^0$ to a string $v = \epsilon$ don't produce any effect, but, applyin $v^0$ to a string $v \ne \epsilon$, where $|v| = l$, it makes the string $v$ empty. Like this: Cases with v and x Is it right? $\endgroup$ – JB-Franco Apr 14 '17 at 0:31

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.