Chapter 6: Context-Free Languages ~ 215
As ;: and ;:1 are the yields of T and a proper subtree T 1 of T, we can write
Z = UZ IY' As ;: 1 and lV are the yields of T 1 and a proper subtree T:. of T 1 , we
can write z1 =vwx. Also, 1vwx 1 > 1w I· SO, I vx I ;::: 1. Thus, we have;: =uvwxy
with 1 vwx 1 ::; 11 and I vx I ;::: 1. This proves the points (i)-(iii) of the theorem.
As T is an S-tree and T 1 , T:. are B-trees, we get S :::b uBy, B :::b vBx and
B :::b w. As S :::b uBy::::;. uwy, uvOwxOy E L. For k ;::: 1, S :::b uBy :::b uvkB./y
:::b U1,kwx.ky E L. This proves the point (iv) of the theorem. I
S
A
B
a
v1
B
b
b
A
a
B
v2
b
B
B
b
Fig. 6.13 Tree T and its subtrees T 1 and h
Co.rnllary Let L be a context-free language and n be the natural number
obtained by using the pumping lemma. Then (i) L =t 0 if and only if there
exists w E L with Iw I < n, and (ii) L is infinite if and only if there exists
z E L such that n ::; 1 z I < 2n.