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 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*}
&amp;S \to A_1 \ldots A_m \\
&amp;A_1 \to A_2 \mid \sigma_1 \\
&amp;A_2 \to A_3 \mid \sigma_2 \\
&amp;\cdots \\
&amp;A_{m-1} \to A_m \mid \sigma_{m-1} \\
&amp;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)$.