216 ~ Theory of Computer Science
Proof (i) We have to prove the 'only if part. If Z E L with 1::1 ;::: n, we
apply the pumping lemma to write z = llVWX.\' , where 1 :s; Ivx I :s; 11. Also,
lfW)' ELand 1Inv)' I < Iz I. Applying the pumping lemma repeatedly, we can
get z' E L such that Iz'l < 11. Thus (i) is proved.
(ii) If z E L such that 11 :s; 1 z I < 211. by pumping lemma we can write
z = llVW.:r)'. Also. llVkW.l)' E L for all k ;::: O. Thus we get an infinite number
of elements in L. Conversely, if L is infinite, we can find z E L with IzI ; : : : 11.
If 1 z i < 2/1. there is nothing to prove. Otherwise, we can apply the pumping
lemma to write z =llVWXJ and get UWJ E L. Every time we apply the pumping
lemma we get a smaller string and the decrease in length is at most n (being
equal to i l'X I). SO. we ultimately get a string z' in L such that n :s; Iz' 1< 2n.
This proves (ii). I
Note: As the proof of the corollary depends only on the length of VX, we can
apply the corollary to regular sets as well (refer to pumping lemma for regular
sets).
The corollary given above provides us algorithms to test whether a given
context-free language is empty or infinite. But these algorithms are not efficient.
We shall give some other algOlithms in Section 6.6.
We use the pumping lemma to show that a language L is not a contextfree language. We assume that L is context-free. By applying the pumping
lemma we get a contradiction.
The procedure can be carried out by using the following steps:
Step 1 Assume L is context-free. Let 11 be the natural number obtained by
using the pumping lemma.
Step 2 Choose z E L so that Iz I ;::: n. Write z = lIVWXJ using the pumping
lemma.
Step 3 Find a suitable k so that 111,kw.l.v E L. This is a contradiction, and so
L is not context-free.
EXAMPLE 6.18
Show that L = {a"b"c" l11 2 I} is not context-free but context-sensitive.
Solution
We have already constructed a context-sensitive grammar G generating L (see
Example 4.11). We note that in every string of L. any symbol appears the
same number of times as any other symbol. Also a cannot appear after b, and
c cannot appear before b. and so 'In.
Step 1 Assume L is context-free. Let 11 be the natura! number obtained by
using the pumping lemma.
Step 2 Let z =a"b"e". Then Iz I =311 > n. Write z =lIVW.\}', where Ivx I 2 1,
i.e. at least one of v or x is not :l\.
Proof (i) We have to prove the 'only if part. If Z E L with 1::1 ;::: n, we
apply the pumping lemma to write z = llVWX.\' , where 1 :s; Ivx I :s; 11. Also,
lfW)' ELand 1Inv)' I < Iz I. Applying the pumping lemma repeatedly, we can
get z' E L such that Iz'l < 11. Thus (i) is proved.
(ii) If z E L such that 11 :s; 1 z I < 211. by pumping lemma we can write
z = llVW.:r)'. Also. llVkW.l)' E L for all k ;::: O. Thus we get an infinite number
of elements in L. Conversely, if L is infinite, we can find z E L with IzI ; : : : 11.
If 1 z i < 2/1. there is nothing to prove. Otherwise, we can apply the pumping
lemma to write z =llVWXJ and get UWJ E L. Every time we apply the pumping
lemma we get a smaller string and the decrease in length is at most n (being
equal to i l'X I). SO. we ultimately get a string z' in L such that n :s; Iz' 1< 2n.
This proves (ii). I
Note: As the proof of the corollary depends only on the length of VX, we can
apply the corollary to regular sets as well (refer to pumping lemma for regular
sets).
The corollary given above provides us algorithms to test whether a given
context-free language is empty or infinite. But these algorithms are not efficient.
We shall give some other algOlithms in Section 6.6.
We use the pumping lemma to show that a language L is not a contextfree language. We assume that L is context-free. By applying the pumping
lemma we get a contradiction.
The procedure can be carried out by using the following steps:
Step 1 Assume L is context-free. Let 11 be the natural number obtained by
using the pumping lemma.
Step 2 Choose z E L so that Iz I ;::: n. Write z = lIVWXJ using the pumping
lemma.
Step 3 Find a suitable k so that 111,kw.l.v E L. This is a contradiction, and so
L is not context-free.
EXAMPLE 6.18
Show that L = {a"b"c" l11 2 I} is not context-free but context-sensitive.
Solution
We have already constructed a context-sensitive grammar G generating L (see
Example 4.11). We note that in every string of L. any symbol appears the
same number of times as any other symbol. Also a cannot appear after b, and
c cannot appear before b. and so 'In.
Step 1 Assume L is context-free. Let 11 be the natura! number obtained by
using the pumping lemma.
Step 2 Let z =a"b"e". Then Iz I =311 > n. Write z =lIVW.\}', where Ivx I 2 1,
i.e. at least one of v or x is not :l\.