# The language L = { $a^nb^mc^n$ | $m \ge n$ } is not context-free. Pumping Lemma through 6 cases.

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:

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!

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$.

• sorry, it's not clear: if there are fewer $a$'s than $c$'s, does $v$ would be equal to $\epsilon$? – JB-Franco Apr 12 '17 at 21:06
• 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? – JB-Franco Apr 12 '17 at 21:16
• 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$. – Magdiragdag Apr 13 '17 at 7:02
• For you second question, $v^0$ is always $\epsilon$, by definition, whatever $v$ is. – Magdiragdag Apr 13 '17 at 7:08
• 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? – JB-Franco Apr 14 '17 at 0:31