Skills101
← All practice quizzes

Quiz: Pumping Lemma and Minimisation

5 questionsNo time limitPass: 60%+10 XP on first pass

How to prove a language is NOT regular with the pumping lemma (aⁿbⁿ, palindromes, prime lengths), the intuition behind it, Myhill–Nerode distinguishability, and minimising a DFA with the partition / table-filling method — implemented in Python.

Log in to take the quiz

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

  1. Question 1

    In a pumping-lemma proof that L is not regular, what do YOU get to choose?

  2. Question 2

    Why is {a^n b^n} not regular?

  3. Question 3

    What can the pumping lemma for regular languages prove?

  4. Question 4

    In the minimisation demo, how many states did the minimal DFA have?

  5. Question 5

    What is the first split in partition-refinement minimisation?