Skills101
← All practice quizzes

Quiz: Pumping Lemma Proofs

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Write pumping lemma proofs that earn full marks. A fixed template, the "game" view of who chooses what, five fully worked proofs (pumping down, square lengths, a closure shortcut, aⁿbⁿcⁿ and ww with the context-free pumping lemma), the classic wrong proofs, and Python that checks every possible split for small p.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    In a pumping lemma proof, who chooses the pumping length p?

  2. Question 2

    For L = {0ⁿ1ᵐ | n > m} with s = 0ᵖ⁺¹1ᵖ, which i breaks every split?

  3. Question 3

    Why can we say y = aᵏ when s = aᵖbᵖ?

  4. Question 4

    For L = {a^(n²)} and s = a^(p²), why is xy²z not in L?

  5. Question 5

    What does this print?

    p = 4
    lengths = [p * p + k for k in range(1, p + 1)]
    print(lengths, (p + 1) ** 2)
    
🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →