Need clarification on pumping lemma for context free languages

Question

I am doing a problem where I am applying pumping lemma to the CFL L = {a^nb^nc^n : n >= 0}. Here is the start of a proof I was looking at:

1. Assume L is a CFL, so there exists a pumping length p for L
2. Choose w = a^p b^p c^p
3. Look at decompositions of uv^ixy^iz where: a. |vy| >= 1 b. |vxy| <= p

The proof then says that there are only these cases to consider, and no other cases are valid to look at:

Case 1-3: v & y only contain as or v & y only contain bs OR v & y only contain cs Case 4-5: v & y contains only as and bs OR v & y contains only bs and cs

Why are these the only cases? Why can't v & y contain as and cs, or v & y contain as, bs, and cs (like, for example v contains as and bs, and y contains bs and cs). The person I saw the solution from explains that because we made each part of the string have length p, trying to have v & y contain as, bs, and cs will go over the pumping length p, but I don't get how it would go over the pumping length. He also doesn't explain why we cant have as and cs in v & y. If anyone could explain how trying to have as, bs, and cs in v & y doesn't work, and why we can't have as & cs only in v & y, I would really appreciate it. Thanks!

Answer 1

Structure

In this case the structure of the string we consider is:

w = uvxyz = a^(p) b^(p) c^(p)

Where the variable p represents the pumping length.

Note that the length of w is thus three times the pumping length.

Redundant case vxy contains a^k b^l c^m

Assume that vxy contained the symbols 'a', 'b', and 'c'. Then we can write this structure as:

• vxy = a^k b^l c^m Such that k + l + m <= p, due to the pumping lemma rules (|vxy| <= p).

However, as the original string has p a's, p b's, and p c's. We know that between the last 'a' and the first 'c' there are p 'b's. This shows that l = p.

Given that: k + l + m <= p, we now know by substituting l for p that: k + p + m <= p, i.e k + m <= 0. This shows that if this case was possible, then k = 0 and l = 0.

Which contradicts our assumption that the case contained the symbols 'a', 'b', 'c', as k and l or both zero thus no 'a' or 'c' symbols are present. Showing that this case is not possible.

vxy contains a^k c^l

If a string contains both 'a' and 'c', then it must also include the 'b' symbols in between as if it contains an 'a' it must go through the 'b' symbols to get to the first 'c'.

This case is thus equivalent to the earlier case, which does not exist.