GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 16

Question

A derivation of a string $w$ of length $n$ in a context-free grammar in Chomsky normal form

• A. must involve exactly $2n-1$ applications of rules for all $n> 0$
• B. must involve at least $2n$ applications of rules for all $n > 0$.
• C. must involve at least $n$ rules, but can involve an arbitrarily large number.
• D. must involve at least $n$ rules and at most $2n$ rules for all $n > 0$.

Answer 1

In CNF, all rules are of the form $A\to BC$ or $A \to a.$ So, to get a string of length $n$ we need $n-1$ steps producing $n$ Non-terminals and then $n$ steps converting these non-terminals to terminals. Thus, we need exactly $n-1+n = 2n-1$ steps.

Correct Answer: A