Use the pumping lemma to show that the language B = {anbncn| n 0} is not

context free.

We assume that B is a CFL and obtain a contradiction. Let p be the pumping

length for B that is guaranteed to exist by the pumping lemma. Select the string

s = apbpcp. Clearly s is a member of B and of length at least p. The pumping

lemma states that s can be pumped, but we show that it cannot. In other words,

we show that no matter how we divide s into uvxyz, one of the three conditions

of the lemma is violated.

First, condition 2 stipulates that either v or y is nonempty. Then we consider

one of two cases, depending on whether substrings v and y contain more than

one type of alphabet symbol.

1. When both v and y contain only one type of alphabet symbol, v does not

contain both as and bs or both bs and cs, and the same holds for y. In

this case, the string uv2xy2z cannot contain equal numbers of as, bs, and

cs. Therefore, it cannot be a member of B. That violates condition 1 of

the lemma and is thus a contradiction.

2. When either v or y contains more than one type of symbol, uv2xy2z may

contain equal numbers of the three alphabet symbols but not in the correct

order. Hence it cannot be a member of B and a contradiction occurs.

One of these cases must occur. Because both cases result in a contradiction, a

contradiction is unavoidable. So the assumption that B is a CFL must be false.

Thus we have proved that B is not a CFL.