🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: CFG and PDA: all 10 questions

Quiz: CFG and PDA · Question 8 of 10

In CNF, how many steps does a derivation of a string of length 5 take?

In CNF, how many steps does a derivation of a string of length 5 take?

  1. A.5
  2. B.8
  3. C.9
  4. D.10
Answer & explanation

Correct answer: 9

A CNF derivation of a length-n string takes 2n − 1 steps: n − 1 uses of A → BC and n uses of A → a.

Can you get the rest right without peeking?

Take the timed Quiz: CFG and PDA quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →