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

computer sciencecontext-free-grammarpumping-lemma

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!

Best Answer

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

Related Question