How can I prove that derivations in Chomsky Normal Form require 2n - 1 steps?

Question

I'm trying to prove the following:

If G is a Context Free Grammar in the Chomsky Normal Form, then for any string w belongs L(G) of length n ≥ 1, it requires exactly 2n-1 steps to make any derivation of w.

How would I go about proving this?

Answer 1

As a hint - since every production in Chomsky Normal Form either has the form

S → AB, for nonterminals A and B, or the form

S → x, for terminal x,

Then deriving a string would work in the following way:

• Create a string of exactly n nonterminals, then
• Expand each nonterminal out to a single terminal.

Applying productions of the first form will increase the number of nonterminals from k to k + 1, since you replace one nonterminal (-1) with two nonterminals (+2) for a net gain of +1 nonterminal. Since your start with one nonterminal, this means you need to do n - 1 productions of the first form. You then need n more of the second form to convert the nonterminals to terminals, giving a total of n + (n - 1) = 2n - 1 productions.

To show that you need exactly this many, I would suggest doing a proof by contradiction and showing that you can't do it with any more or any fewer. As a hint, try counting the number of productions of each type that are made and showing that if it isn't 2n - 1, either the string is too short, or you will still have nonterminals remaining.

Hope this helps!