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

Quiz: Pumping Lemma and Minimisation: 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 that L is not regular, what do YOU get to choose?
  2. Q2. Why is {a^n b^n} not regular?
  3. Q3. What can the pumping lemma for regular languages prove?
  4. Q4. In the minimisation demo, how many states did the minimal DFA have?
  5. Q5. What is the first split in partition-refinement minimisation?
  6. Q6. In the pumping lemma, why must the loop y satisfy |xy| ≤ p?
  7. Q7. To prove palindromes over {a, b} are not regular, which string is a good choice?
  8. Q8. Two strings x and y are distinguishable for L when:
  9. Q9. What does this print? (code)
  10. Q10. What is the first step of DFA minimisation, before splitting into groups?