For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎2+3𝑘…
2019
For Σ = {𝑎, 𝑏}, let us consider the regular language 𝐿 = { 𝑥 |𝑥 = 𝑎2+3𝑘 or 𝑥 = 𝑏10+12𝑘 , 𝑘 ≥ 0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for 𝐿 ?
- A.
3
- B.
5
- C.
9
- D.
24
Attempted by 67 students.
Show answer & explanation
Correct answer: D
Key idea: pick a pumping length that lets us find a pumpable block y whose length is a multiple of the period for each part of the language.
For strings consisting of a's (allowed lengths are 2 (mod 3)): choose y of length 3 inside the first p characters. Pumping repeats y by multiples of 3, so the length stays 2 (mod 3). This requires p ≥ 3.
For strings consisting of b's (allowed lengths are 10 (mod 12)): choose y of length 12 inside the first p characters. Pumping repeats y by multiples of 12, so the length stays 10 (mod 12). This requires p ≥ 12.
Conclusion: any pumping length p that satisfies both requirements (p ≥ 12 and p ≥ 3) will work; in particular p = 24 satisfies p ≥ 12, so 24 can be a pumping length for the language.
A video solution is available for this question — log in and enroll to watch it.