Project ForgeFor Σ={a,b}, let us consider the regular language L = {x | x=a^(2+3k) or x=b^(10+12k), k≥0}. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
- A3
- B5
- C9
- 24
Explanation
Consider the shortest b-string in L, b^10. If p≤10, this string must satisfy pumping, requiring some non-empty y (with |y|≤p≤10) whose length is a multiple of 12 (to preserve the 10+12k form when pumped) — impossible since 0<|y|≤10<12. So any valid p must exceed 10. For p≥12, every sufficiently long b-string has a contiguous run of 12 b's within its first p characters that can be used as y (preserving the period), and a-strings only need p≥3 to find a valid multiple-of-3 y. Among the options, only p=24 (≥12) avoids the b^10 counterexample; p=3,5,9 are all ≤10 and fail.
Source: GATE CS 2019 (Set-2) (2019)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.