# Understanding a bound for derivation length of any string in Pumping lemma for context-free languages

The following is a proof of the pumping lemma for context-free languages from Theorem 8.1 in "An Introduction to Formal Languages and Automata (6th ed.)" by Peter Linz:

Let $$L$$ be an infinite context-free language. Then there exists some positive integer $$m$$ such that any $$w\in L$$ with $$|w|\ge m$$ can be decomposed as

$$w=uvxyz,$$ with

$$|vxy|\le m,$$ and

$$|vy|\ge1,$$ such that

$$uv^ixy^iz\in L,$$ for all $$i=0,1,2,\cdots$$. This is known as the pumping lemma for context-free languages.

Proof: Consider the language $$L−\{\lambda\}$$, and assume that we have for it a grammar $$G$$ without unit-productions or $$\lambda$$-productions. Since the length of the string on the right side of any production is bounded, say by $$k$$, the length of the derivation of any $$w\in L$$ must be at least $$|w|/k$$. Therefore, since $$L$$ is infinite, there exist arbitrarily long derivations and corresponding derivation trees of arbitrary height.

...

I don't understand that "Since the length of the string on the right side of any production is bounded, say by $$k$$, the length of the derivation of any $$w\in L$$ must be at least $$|w|/k$$".

Specifically, where does the "$$|w|/k$$" come from?

Consider a word $$x\in (V\cup \Sigma)^*$$. Applying a derivation rule on $$x$$ to derive a word $$x'\in (V\cup \Sigma)^*$$ adds at most $$k-1$$ symbols, that is, $$|x'| \leq |x|+k-1$$. Therefore, if $$S=x_0, x_1, x_2, \ldots, x_t = w$$ is a derivation sequence of $$w$$, then by an iterative application of what we've established above, we have that $$|w|=|x_t| \leq |x_{t-1}| + k -1 \leq |x_{t-2}| + 2k -2 \leq \cdots \leq |x_{t-t}| + tk - t$$ $$= |S| + tk-t = tk -t + 1$$
and so $$t\geq \frac{|w|-1}{k-1}$$.
• Because $k\le|w|$, the $\frac{|w|-1}{k-1}\ge\frac{|w|}{k}$ holds so that we get $t\ge\frac{|w|}{k}$. Commented Aug 1 at 4:45