Question

Use the pumping lemma to show that the following languages are not context free:

a)0^n0^2n0^3n;n>=0
b) {w#x \ where w.x e {a,b) * and w is a substring of x}
c) (a^ib^ja^ib^j|i,j>0)

Answer 1

Language L = i,j,k >= 0 and i = k or j = k

Assume L is context-free. By the pumping lemma, there exists a pumping length p such that any string w in L with |w| >= p can be written as w = uvxyz where |vxy| <= p, |vy| >= 1, and uv^nxy^n is also in L for all n>=0.

Choose w = 0^p1^p0^p. By L's definition, i = k = p and j can be any non-negative integer. Thus, w is in L.

Next, consider all possible ways to divide vxy into three parts: v, x, and y. There are three cases:

1. vxy contains only 0's. In this case, pumping up will increase the number of 0's in the first section but not the second and third sections, resulting in a string that is not in L.

2. vxy contains only 1's. In this case, pumping up will increase the number of 1's in the second section but not the first and third sections, resulting in a string that is not in L.

3. vxy contains both 0's and 1's. In this case, pumping up will cause v and y to overlap the first and third sections, resulting in a string with unequal numbers of 0's in the first and third sections, which is not in L.

Therefore, L cannot be context-free, since the pumping lemma has been violated.