← 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?
- A.Because every string in L has length at most p
- B.Because a DFA with p states must repeat a state within its first p symbols
- C.Because y must be the last symbol
- 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 →