To obtain a string of n Terminals from a given Chomsky normal form grammar,…

Key idea: In Chomsky normal form (CNF) every production is either a binary rule of the form variable -> variable variable or a terminal rule of the form variable -> terminal.

Reasoning:

• To produce n terminals you must use exactly n terminal rules (one variable -> terminal for each terminal).

• To combine these n terminals into a single start symbol using only binary rules, you form a binary parse tree with n leaves. A binary tree with n leaves has exactly n - 1 internal binary nodes, each corresponding to one binary production (variable -> variable variable).

Total productions used = number of terminal rules + number of binary rules = n + (n - 1) = 2n - 1.

Example (n = 3):

1. You need 3 terminal productions to produce the three terminals.

2. You need 2 binary productions to join them into one tree (a binary tree with 3 leaves has 2 internal nodes).

3. Total = 3 + 2 = 5 = 2n - 1.

Therefore the number of productions used to obtain a string of n terminals from a CNF grammar is 2n - 1.