If the parse tree of a word w generated by a Chomsky normal form grammar has…
2012
If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length
- A.
no greater than 2^(i+1)
- B.
no greater than 2^i
- C.
no greater than 2^(i−1)
- D.
no greater than i
Attempted by 44 students.
Show answer & explanation
Correct answer: C
In Chomsky Normal Form, internal nodes have exactly two children. A path of length i defines the tree height in edges. Consequently, the maximum number of terminal symbols generated is 2 to the power of i.
A video solution is available for this question — log in and enroll to watch it.