🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← All topics

Quiz: CFG and PDA: questions with answers

10 questions, each with the answer and a short explanation.

Take the timed quiz + get a certificate →
  1. Q1. Which grammar generates {a^n b^n | n ≥ 0}?
  2. Q2. How many parse trees did the ambiguous grammar E → E+E | EE | id give for id+idid?
  3. Q3. What extra memory does a pushdown automaton have compared with a finite automaton?
  4. Q4. Context-free languages are NOT closed under:
  5. Q5. What is the time complexity of the CYK algorithm for a string of length n?
  6. Q6. Which derivation of aabb uses the grammar S → aSb | ε correctly?
  7. Q7. A grammar is ambiguous when:
  8. Q8. In CNF, how many steps does a derivation of a string of length 5 take?
  9. Q9. What does this print? (code)
  10. Q10. Why are deterministic PDAs weaker than nondeterministic PDAs?