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?
Answer: C. 2l − 1 — 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…
- A.
2l
- B.
2l + 1
- C.
2l − 1
- D.
l
Attempted by 144 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2