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…

  1. A.

    3

  2. B.

    5

  3. C.

    9

  4. 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

Loading lesson…