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

Quiz: Pumping Lemma Proofs: questions with answers

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

Take the timed quiz + get a certificate →
  1. Q1. In a pumping lemma proof, who chooses the pumping length p?
  2. Q2. For L = {0ⁿ1ᵐ | n m} with s = 0ᵖ⁺¹1ᵖ, which i breaks every split?
  3. Q3. Why can we say y = aᵏ when s = aᵖbᵖ?
  4. Q4. For L = {a^(n²)} and s = a^(p²), why is xy²z not in L?
  5. Q5. What does this print? (code)
  6. Q6. How does the closure-property proof show {aⁱbʲ | i ≠ j} is not regular?
  7. Q7. In the pumping lemma for context-free languages, which conditions hold for the split s = uvwxy?
  8. Q8. Why can't the window vwx of aᵖbᵖcᵖ change all three letter counts?
  9. Q9. A student writes: "Let x = ε, y = a, z = aᵖ⁻¹bᵖ. Then xy²z ∉ L, so L is not regular." What is wrong?
  10. Q10. Which of these languages IS context-free?