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 πΏ ?
Answer: D. 24 β 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β¦
- A.
3
- B.
5
- C.
9
- D.
24
Attempted by 85 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.
Explore the full course: Iocl Engineers Officers Grade A Paper 2