To obtain a string of n terminals from a given Chomsky normal form grammar,…
2018
To obtain a string of n terminals from a given Chomsky normal form grammar, the number of productions to be used is
- A.
2n-1
- B.
2n
- C.
n + 1
- D.
n²
Attempted by 56 students.
Show answer & explanation
Correct answer: A
In Chomsky Normal Form, productions are either binary (A -> BC) or terminal (A -> a). To generate a string of length n, the derivation tree has n leaves. This requires exactly 2n - 1 production steps in total, comprising n terminal productions and n-1 binary productions.
A video solution is available for this question — log in and enroll to watch it.