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

Quiz: Simplifying CFGs and CNF: questions with answers

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

Take the timed quiz + get a certificate →
  1. Q1. In the grammar S → AB | a, A → b, B → BC, C → c, which variable is not generating?
  2. Q2. Why must non-generating symbols be removed before unreachable ones?
  3. Q3. In S → ASA | aB, A → B | S, B → b | ε, which variables are nullable?
  4. Q4. A rule A → XYZ has X and Z nullable. How many non-empty bodies does it give after ε-removal?
  5. Q5. What does this print? (code)
  6. Q6. Which of these is a unit production?
  7. Q7. Why are ε-productions removed before unit productions?
  8. Q8. Which rule is allowed in Chomsky Normal Form?
  9. Q9. How many new variables are needed to split A → BCDEF into CNF pairs (no reuse)?
  10. Q10. What does this print? (code)