Ullman (TOC) Edition 3 Exercise 7.1 Question 8 (Page No. 278)

Question

Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$

1. Show that the CNF grammar has at most $O(n^{2})$ productions.
2. Show that it is possible for the $CNF$ grammar to have a number of productions proportional to $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.