🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Pumping Lemma and Minimisation: all 10 questions

Quiz: Pumping Lemma and Minimisation · Question 6 of 10

In the pumping lemma, why must the loop y satisfy |xy| ≤ p?

In the pumping lemma, why must the loop y satisfy |xy| ≤ p?

  1. A.Because every string in L has length at most p
  2. B.Because a DFA with p states must repeat a state within its first p symbols
  3. C.Because y must be the last symbol
  4. D.Because x must be empty
Answer & explanation

Correct answer: Because a DFA with p states must repeat a state within its first p symbols

By the pigeonhole principle, some state repeats while reading the first p symbols, so the loop lies there.

Can you get the rest right without peeking?

Take the timed Quiz: Pumping Lemma and Minimisation quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →