Question

Prove a language {ww^R0^m where w^R is the reverse of w and w has m 0’s } is not context-free using the pumping lemma.

Answer 1

The Pumping Lemma for Context-free Languages: An Example
Claim 1 The language
n
wwRw | w ∈ {0, 1}
∗
o
is not context-free.
Proof: For the sake of contradiction, assume that the language L = {wwRw | w ∈ {0, 1}
∗} is
context-free. The Pumping Lemma must then apply; let k be the pumping length. Consider the
string
s =
w
z }| {
0
k
1
k
wR
z }| {
1
k
0
k
w
z }| {
0
k
1
k = 0k
1
2k
0
2k
1
k ∈ L.
Since |s| ≥ k, it must be possible to split s into five pieces uvxyz satisfying the conditions of the
Pumping Lemma. The substrings v and y must collectively contain some symbols since |vy| > 0.
We consider the following exhaustive cases.
1. The substrings v and/or y contain some symbols from the first block of k 0s. Since |vxy| ≤ k,
v and y cannot contain any 0s from the second block of 2k 0s. Consider the string uv0xy0
z =
uxz. The string uxz must be of the form 0i1 1
i2 0
2k1
k where i1 < k and i2 ≤ 2k. If uxz ∈ L, it
must be of the form ααRα. Since uxz is of the form 0i1 1
i2 0
2k1
k and of length at least 5k, the
first α must begin with the block of i1 < k 0s followed by some number of 1s. Thus, α
Rα must
contain a block of at most 2i1 < 2k 0s. But uxz contains a block of 2k 0s, a contradiction.
2. The substrings v and/or y contain some symbols from the first block of 2k 1s. Since |vxy| ≤ k,
v and y cannot contain any 1s from the second block of k 1s. Consider the string uv0xy0
z =
uxz. The string uxz must be of the form 0i1 1
i2 0
i3 1
k where i1 ≤ k, i2 < 2k, and i3 ≤ 2k. If
uxz ∈ L, it must be of the form ααRα. Since uxz is of the form 0i1 1
i2 0
i3 1
k and of length at
least 5k, the last α must end with the block of k 1s preceded by some number of 0s. Thus,
ααR must contain a block of 2k 1s. But uxz contains a block of i2 < 2k 1s, a contradiction.
3. The substrings v and/or y contain some symbols from the second block of 2k 0s. Since
|vxy| ≤ k, v and y cannot contain any 0s from the first block of k 0s. Consider the string
uv0xy0
z = uxz. The string uxz must be of the form 0k1
i1 0
i2 1
i3 where i1 ≤ 2k, i2 < 2k, and
i3 ≤ k. If uxz ∈ L, it must be of the form ααRα. Since uxz is of the form 0k1
i1 0
i2 1
i3 and
of length at least 5k, the first α must begin with the block of k 0s followed by some number
of 1s. Thus, α
Rα must contain a block of 2k 0s. But uxz contains a block of i2 < 2k 0s, a
contradiction.
4. The substrings v and/or y contain some symbols from the second block of k 1s. Since |vxy| ≤ k,
v and y cannot contain any 1s from the first block of 2k 1s. Consider the string uv0xy0
z = uxz.
The string uxz must be of the form 0k1
2k0
i1 1
i2 where i1 ≤ 2k and i2 < k. If uxz ∈ L, it
must be of the form ααRα. Since uxz is of the form 0k1
2k0
i1 1
i2 and of length at least 5k,the second α must end with the block of i2 < k 1s preceded by some number of 0s. Thus,
ααR must contain a block of at most 2i2 < 2k 1s. But uxz contains a block of 2k 1s, a
contradiction.
Thus, the Pumping Lemma is violated under all circumstances, and the language in question cannot
be context-free. ✷
Note that the choice of a particular string s is critical to the proof. One might think that
any string of the form wwRw would suffice. This is not correct, however. Consider the trivial
string 0k0
k0
k = 03k which is of the form wwRw. Letting v = 0, x = ε, and y = 00, we have
uvixyi
z = 03(k+i−1) which is an element of L since it is a string consisting of a multiple of three
0s. The above argument can be generalized for any string of the form p
3k where p is a palindrome.
Furthermore, seemingly “good” strings such as
s =
w
z}|{
0
k
1
wR
z}|{
10k
w
z}|{
0
k
1 = 0k
1102k
1
can also be pumped: let v = 0, x = 11, and y = 00 (i.e., v consists of the 0 immediately preceding
the 11, x is the 11, and y consists of the two 0s immediately following the 11). We then have
uvixyi
z = 0k+i−11102(k+i−1)1 which is an element of L for all i since uvixyi
z = ααRα where
α = 0k+i−11. Again, the choice of the string to be pumped is critical.