# Space complexity of Chomsky Normal Form

I'm trying to find sup of $\|\mathbb{G}\|$ where $\mathbb{G}$ is CFG in Chomsky Normal Form. So far i have done some work, but I'm really not sure in my proof. Let $G = \langle Q, N, S, R\rangle$ and $$\alpha \rightarrow \beta \in R,\ |\beta| = n$$ $$\|\alpha\| \le \sum_{i=0}^{\log_{2}n}2^{n}\,.$$ I made this conclusion by observing the binary tree I get when I try substituting the right side of the rule with $$\beta =b_{1}b_{2}...b_{n}$$ $$\beta \rightarrow A_{1}A_{2},A_{1}\rightarrow B_{1}B_{2}, A_{2}\rightarrow B_{3}B_{4}$$ and so on until $$Q_{1} \rightarrow b_{1}b_{2}, ...,Q_{[\frac{n}{2}]}\rightarrow b_{n-1}b_{n}$$

The result is binary tree with height $\log_{2}n$ which on each level has $2^{i}, i = {0,1,...,\log_{2}n}$ nodes. Finally I claim that $$\|\mathbb{G}\| \le |N| + |N|\sum_{i=0}^{|N|-1}(\|\alpha\|),\ \exists (A \rightarrow \alpha) \in R\,.$$

• It would probably help to spell out "CNF" in the title at least because everyone will assume you mean conjunctive normal form Boolean formulas. – David Richerby Jun 29 '17 at 14:50
• Oh, i really didn't mean that. Thank you! – Zarrie Jun 29 '17 at 15:49

It is well-known, and stated in Wikipedia (which gives a reference: Lange and Leiß), that there is an algorithm transforming an arbitrary context-free grammar $G$ into a grammar in Chomsky normal form of size $O(|G|^2)$.
The following grammar might be an example showing that the quadratic blow-up is necessary: \begin{align*} &S \to A_1 \ldots A_m \\ &A_1 \to A_2 \mid \sigma_1 \\ &A_2 \to A_3 \mid \sigma_2 \\ &\cdots \\ &A_{m-1} \to A_m \mid \sigma_{m-1} \\ &A_m \to \sigma_m \end{align*} This grammar has size $\Theta(m)$, and it seems that every grammar in Chomsky normal form for this language must have size $\Omega(m^2)$.