Chapter 6: Context-Free Languages l;! 213
Step 3 A 6 ----,> A(l~ lAs can be modified by using Lemma 6.2. The resulting
productions give all the A 6 -productions:
A6 ----,> (A0:;A~A-l1 aA~A-l1 (A03ZSAY~-l
A 6 ----,> aZy4~A41 (A c 03 I a
(6.15)
A 6 ----,> (A03A~A-lZ61 aA~A4Z61 (A03ZsA~A4Z6
A 6 ----,> aZsA~A-lZ61 (A03Z61 aZ6
(6.16)
A 6 ----,> AIAsiAIAsZ6
Step 4 The step is not necessary as A,productions for i = 5, 4, 3, 2, 1 are
in the required form.
Step 5 The Zs-productions are Zs ----,> A~A41 A~A4ZS' These can be modified
as
Zs ----,> 'A-ll" A-lZ s
(6.17)
The Z6-productions are Z6 ----,> A lAs IA jA S Z 6 . These can be modified as
Z6 ----,> + k" 1+ A S Z 6
(6.18)
The required grammar in Gl\;Tf is given by (6.13)-(6.18).
6.5 PUMPING LEMMA FOR CONTEXT-FREE
LANGUAGES
The pumping lemma for context-free languages gives a method of generating
an infinite number of strings from a given sufficiently long string in a contextfree language L. It is used to prove that certain languages are not context-free.
The construction \ve make use of in proving pumping lemma yields some
decesion algorithms regarding context-free languages.
Lemma 6.3 Let G be a context-free grammar in CNF and T be a delivation
tree in G. If the length of the longest path in T is less than or equal to k, then
the yield of T is of length less than or equal to 21:-1.
Proof We prove the result by induction on k, the length of the longest path
for all A-trees (Recall an A-tree is a derivation tree whose root has label A).
\~'hen the longest path in an A-tree is of length 1. the root has only one son
whose label is a terminal (when the root has two sons, the labels are variables).
So the yield is of length 1. Thus. there is basis for induction.
Assume the result for k - 1 (k > 1). Let T be an A-tree with a longest path
of length less than or equal to k. As k > 1. the root of T has exactly two sons
with labels A j and A~. The two subtrees with the t\VO sons as roots have the
longe::t paths of length less than or equal to k - 1 (see Fig. 6.12).
If WI and ,v~ are their yields. then by induction hypothesis, IWI I :::; 21:-~,
I,v~ I :::; 21:-~. So the yield of T = WI We' I WI H': I :::; 21:-: + 21:-~ = 21:-1. By the
principle of induction, the result is true for all A-trees. and hence for all
derivation trees.
Step 3 A 6 ----,> A(l~ lAs can be modified by using Lemma 6.2. The resulting
productions give all the A 6 -productions:
A6 ----,> (A0:;A~A-l1 aA~A-l1 (A03ZSAY~-l
A 6 ----,> aZy4~A41 (A c 03 I a
(6.15)
A 6 ----,> (A03A~A-lZ61 aA~A4Z61 (A03ZsA~A4Z6
A 6 ----,> aZsA~A-lZ61 (A03Z61 aZ6
(6.16)
A 6 ----,> AIAsiAIAsZ6
Step 4 The step is not necessary as A,productions for i = 5, 4, 3, 2, 1 are
in the required form.
Step 5 The Zs-productions are Zs ----,> A~A41 A~A4ZS' These can be modified
as
Zs ----,> 'A-ll" A-lZ s
(6.17)
The Z6-productions are Z6 ----,> A lAs IA jA S Z 6 . These can be modified as
Z6 ----,> + k" 1+ A S Z 6
(6.18)
The required grammar in Gl\;Tf is given by (6.13)-(6.18).
6.5 PUMPING LEMMA FOR CONTEXT-FREE
LANGUAGES
The pumping lemma for context-free languages gives a method of generating
an infinite number of strings from a given sufficiently long string in a contextfree language L. It is used to prove that certain languages are not context-free.
The construction \ve make use of in proving pumping lemma yields some
decesion algorithms regarding context-free languages.
Lemma 6.3 Let G be a context-free grammar in CNF and T be a delivation
tree in G. If the length of the longest path in T is less than or equal to k, then
the yield of T is of length less than or equal to 21:-1.
Proof We prove the result by induction on k, the length of the longest path
for all A-trees (Recall an A-tree is a derivation tree whose root has label A).
\~'hen the longest path in an A-tree is of length 1. the root has only one son
whose label is a terminal (when the root has two sons, the labels are variables).
So the yield is of length 1. Thus. there is basis for induction.
Assume the result for k - 1 (k > 1). Let T be an A-tree with a longest path
of length less than or equal to k. As k > 1. the root of T has exactly two sons
with labels A j and A~. The two subtrees with the t\VO sons as roots have the
longe::t paths of length less than or equal to k - 1 (see Fig. 6.12).
If WI and ,v~ are their yields. then by induction hypothesis, IWI I :::; 21:-~,
I,v~ I :::; 21:-~. So the yield of T = WI We' I WI H': I :::; 21:-: + 21:-~ = 21:-1. By the
principle of induction, the result is true for all A-trees. and hence for all
derivation trees.