🎙 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 6 of 10

Which derivation of aabb uses the grammar S → aSb | ε correctly?

Which derivation of aabb uses the grammar S → aSb | ε correctly?

  1. A.S ⇒ aSb ⇒ aaSbb ⇒ aabb
  2. B.S ⇒ aSb ⇒ abSab ⇒ aabb
  3. C.S ⇒ ab ⇒ aabb
  4. D.S ⇒ aaSbb ⇒ aSb ⇒ aabb
Answer & explanation

Correct answer: S ⇒ aSb ⇒ aaSbb ⇒ aabb

Each step replaces S by aSb, and the last step uses S → ε.

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 →