Computational Theory: Proof, Chomsky normal form Prove or disprove: If $G$ is a CFG in Chomsky normal form, then for any string $w \in L(G)$ of length $n\geq 1$ then exactly $2n-1$ steps are required for any derivation of $w$.
I'm stuck at where to start with this proof... When i see the $2n-1$ it leads me to believe that I should utilize the pigeon hole principle. However, i'm also thinking it would be more thorough to prove this by doing a proof by construction. Any help is appreciated. 
 A: It's an old post, but I'm interested in this proof. I don't find the other answer correct. Instead I found another solution. First we prove the following theorem:
Theorem 1
Consider a derivation $\mathcal{D}$ of some word $w\in L$, where $|w|\gt 0$. For any subderivation $\mathcal{D'}$ of $\mathcal{D}$ that produces a substring of $w$ with length $k>0$, $\mathcal{D'}$ uses exactly $2k-1$ production steps.
Proof: By induction on the structure of the subderivation.


*

*Case $S\to\varepsilon$: This case is irrelevant since it doesn't produce a word of length greater than 0.

*Case $A\to a$: Indeed, such a subderivation produces a string of length 1 in $1=2\cdot 1 - 1$ production steps.

*Case $A\to BC$: Let $k_B$ and $k_C$ be the lengths of the substrings of $w$ that are produced by the subderivations that start from $B$ and $C$, respectively. Obviously, $k = k_B + k_C$. Since $B\neq S$ and $C\neq S$, we have $k_B > 0$ and $k_C > 0$. By the induction hypothesis, the two subderivations use $2 k_B - 1$ and $2 k_C - 1$ production steps, respectively. Then, the whole derivation uses $(2\cdot k_B - 1) + (2\cdot k_C - 1) + 1 = 2 k - 1$.


Qed.
The statement in the question follows by instantiating $k$ with $|w|$ in the above theorem. The theorem requires that $k>0$, so we have to be careful that $|w| >0$. That's no problem, because $|w|>0$ is also a requirement of the theorem.

Edit: Theorem 1 above can be rephrased to
Theorem 1': For any derivation, $A\to\ldots\to w$ produced by the rules of some context free grammar in CNF, where $A$ is a non-terminal and $|w|>0$, that derivation uses $2|w|−1$ steps.
Then, the statement of the question follows as a corollary of Theorem 1', where we set $A$ to be specifically the starting symbol of the grammar and not just any non-terminal.
