DHARM316 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCEAssume length of largest path is k(k >1) then the sub trees TB and TC has the largest
path is ≤ (k – 1).
From the binary tree properties we know that tree extended up to level (k – 1) yields a
string of length at most 2k–2. So, the sub trees TB and TC each yields the substrings of at most
2 k–2. Because A ⇒ BC ⇒ terminal string; whose yield is the concatenation of yields of tree TB
and yields of tree TC. That is, at most of
2 k–2 + 2k–2 = 2. 2k–2
= 2k–1 (so the fact is true)
Similarly using method of induction we can see that for any k = n above fact is true.
Pumping lemma
If G be CFG then there exist a constant n such that if Z is any string s.t. Z ∈ L(G) and | Z | ≥n
then Z can be written as
G = u.v.w.x.y
where,
i. |v.x| ≥ 1
ii. |v.w.x| ≤ n
iii. ∀i ≥ 0, u.vi.w.xi.y ∈ L(G)
Proof. We construct the proof for the CNF that of the CFG G = (VN, VT, S, P). Assume the
grammar has k non terminals i.e.,
| VN | = k
Let the constant n = 2k and assume a string Z that is in L(G) with | Z | ≥ n.
Now, consider the derivation tree for the string Z and apply the above fact. Since, G has
k non terminals and a type of GNF so the length of the largest path in the derivation tree is at
most k that yields the string of length at most (2k – 1).
i.e., 2 k–1 = 2k/2 = n/2
So, the grammar G generates the string of length at most of n/2.
Although we assume that the string | Z | ≥ n but the derivation tree yields the string of
length = n/2 (≠ n).
So, the derivation tree that yields the string Z where | Z | ≥ n has the path length
more than k or at least (k + 1).
Draw the derivation tree that has one of the path lengths at least (k + 1). Hence the
number of nodes (non terminals) in the path is at least (k + 2).
Since, G has only k different non terminals thus this path has at least two duplicate non
terminals so that total number of non terminals becomes at least (k + 2).
Fig. 11.26 shows that X, Y, A .....are k non terminals and assume symbol A occurs at
least twice in the path. Then it is possible to divide the tree as shown in Fig. 11.26.