If the parse tree of a word w generated by a grammar in Chomsky normal form…

Concept

In Chomsky normal form, every nonterminal production either branches into exactly two nonterminals or produces one terminal symbol.

A binary tree with h branching levels has at most 2h leaves. The terminal-production edge does not create another binary branch.

Application

1. Let the maximum root-to-terminal path length be i edges.

2. The final edge produces a terminal symbol, so at most i − 1 earlier levels can contain binary branching.

3. Starting with one root, each binary level can double the number of leaves; after at most i − 1 branching levels, there are at most 2i − 1 leaves.

4. Each terminal leaf contributes one symbol to w, so the length of w is at most 2i − 1.

Cross-check and contrast

For i = 1, only a direct nonterminal-to-terminal production is possible and the bound gives 1. Each additional allowed edge can add one binary level and double the maximum yield.

• 2i + 1 counts two more binary levels than the tree permits.

• 2i treats the terminal-production edge as if it were another binary level.

• 2i − 1 reserves the final edge for producing terminals and counts only the binary levels.

• i grows linearly, whereas a binary parse tree can double its yield at each branching level.

Therefore, the word length is no greater than 2i − 1.