If G is a context-free grammar and W is a string of length l in L(G), how long…
1992
If G is a context-free grammar and W is a string of length l in L(G), how long is a derivation of W in G, if G is in Chomsky normal form?
- A.
2l
- B.
2l + 1
- C.
2l − 1
- D.
l
Attempted by 57 students.
Show answer & explanation
Correct answer: C
In Chomsky normal form, every production rule is either of the form A → BC or A → a. To derive a string of length l, we need exactly l terminal productions and l-1 binary splits. Therefore, the total derivation length is 2l - 1 steps.
A video solution is available for this question — log in and enroll to watch it.