Let \(𝐺=(𝑉,𝑇,𝑆,𝑃)\) be any context-free grammar without any \(𝜆-\)…

Goal: derive an upper bound on the number of productions in an equivalent Chomsky Normal Form (CNF) grammar for a grammar without λ-productions or unit productions, where K is the maximum length of any right-hand side and |P| is the number of productions.

• Binarization of long right-hand sides: A production with r symbols on the right-hand side (r ≥ 2) can be converted to a chain of binary productions. This replacement yields r-1 productions in the CNF grammar (for example: A → X1 X2 … Xr becomes A → X1 Y1, Y1 → X2 Y2, …, Y_{r-2} → X_{r-1} Xr).

• Sum over all productions: If the original productions have lengths r1, r2, …, r_|P|, the total number of productions after binarization is ∑(ri − 1) = (∑ri) − |P|. Since each ri ≤ K, this is at most (K − 1)|P|.

• Handling terminals inside longer right-hand sides: For any terminal that appears in the middle of a longer right-hand side, introduce a single new nonterminal that produces that terminal. At most |T| such new productions of the form A_t → a are needed (one per terminal).

Conclusion: combining the binarization count and the terminal replacements gives an upper bound of (K − 1)|P| + |T| productions in an equivalent CNF grammar.

Note: A → a productions that already have a single terminal on the right-hand side are already in CNF and do not need further modification; the |T| term covers the extra productions introduced for terminals that occur inside longer right-hand sides.