If the parse tree of a word w generated by a grammar in Chomsky normal form…
2012
If the parse tree of a word w generated by a grammar in Chomsky normal form has no root-to-leaf path of length greater than i (where path length is the number of edges), which of the following is the tightest upper bound on the length of w?
Answer: C. no greater than 2i − 1 — ConceptIn Chomsky normal form, every nonterminal production either branches into exactly two nonterminals or produces one terminal symbol. A binary tree with…
- A.
no greater than 2i + 1
- B.
no greater than 2i
- C.
no greater than 2i − 1
- D.
no greater than i
Attempted by 4 students.
Show answer & explanation
Correct answer: C
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
Let the maximum root-to-terminal path length be i edges.
The final edge produces a terminal symbol, so at most i − 1 earlier levels can contain binary branching.
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.
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.