For Sigma = {a, b}, let us consider the regular language L = {x | x = a^(2n-18) or x = b^(3n+18), for some n >= 0, with 2n-18 >= 0}.
Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
A. 3
B. 5
C. 9
D. 24
GATE 2019 · Theory of Computation · Pumping Lemma · medium
Answer: D. 24 is a valid pumping length for L. The shortest b-string (b^18) has length 18 < 24, so it need not be pumpable. All strings in L of length >= 24 can be pumped while staying in L.
Identify the structure of L: Part 1: 2n - 18 >= 0 means n >= 9. The values of 2n-18 for n = 9, 10, 11,... are 0, 2, 4, 6,... So part 1 is {epsilon, a^2, a^4, a^6, ...} = all even-length strings of a's (including empty).
Part 2: 3n+18 for n >= 0 gives 18, 21, 24, 27,... So part 2 is {b^18, b^21, b^24,...}.
Check pumping length p = 3: Consider the string a^4 in L (|a^4| = 4 >= 3). We must split as xyz with |xy| <= 3, |y| >= 1. So y = a^k for 1 <= k <= 3. Then xy^0 z = xz = a^(4-k). For this to be in L, 4-k must be even, so k must be even. But k can be 1 (odd), in which case a^3 would need to be in L, but a^3 is not (since part 1 requires even exponent). So p=3 fails.
Check pumping length p = 5: For p=5, consider any string s in L with |s| >= 5. Case 1: s = a^(2m) for m >= 3 (|s| >= 6 >= 5). Split as x=epsilon, y=a^2, z=a^(2m-2). Then |xy|=2<=5, |y|=2>=1, and xy^i z = a^(2i + 2m-2) = a^(2(i+m-1)) which is even for all i >= 0 -- in L. Case 2: s = b^(3n+18) with |s| >= 5 means b^18 or longer. Split y = b^3. Then xy^i z = b^(3n+18 - 3 + 3i) = b^(3(n+i-1)+18) -- in L for i >= 1. For i=0: b^(3n+15) which is not in L since 3n+15 < 18 requires n < 1, and for n >= 1 we get b^(3n+15) which equals b^(3(n-1)+18) -- this IS in L for n >= 1! For n=0: b^15, which needs to be checked: 15 = 3n+18 means n=-1, not valid. Hmm, b^15 not in L. But b^18 (n=0) with y=b^3: pumping down gives b^15, not in L. So y=b^3 doesn't work directly for b^18. Instead use y=b^3 with |xy| <= 5, so we can choose y=b^3 starting at any position. b^18 split as x=b^0, y=b^3, z=b^15 -- i=0 gives b^15 not in L.
Actually for p=5, the valid pumping approach for b^18 (|b^18|=18 >= 5): choose y = b^3, but we need xy^i z in L for all i. xy^0 z = b^15 is not in L. This seems to fail.
However, the pumping lemma says there EXISTS a decomposition xyz -- not that EVERY decomposition works. For b^18: x = b^0, y = b^3, z = b^15 -- pumping UP: b^18+3i in L for i >= 0 since 18+3i = 3(i+0)+18, yes! But i=0 gives b^15... wait i=0: xy^0 z = xz = b^0 b^15 = b^15, not in L. So this decomposition fails for i=0.
The pumping lemma requires xy^i z in L for ALL i >= 0. So b^18 with ANY split where |xy|<=5, |y|>=1 must allow pumping. All such y have y = b^k, 1 <= k <= 5. xy^0 z = b^(18-k). 18-k in {13,14,15,16,17} -- none of these are in L (L requires b^18 or more with step 3). So p=5 fails for b^18!
Let me reconsider. p=24 might be needed since shortest b-string is b^18 and we can only pump b-strings of length >= 18. But for b^18: if p=24, then b^18 has length 18 < 24, so the pumping condition doesn't apply to it. We only need to pump strings of length >= p. For p=24, strings of length < 24 in L need not be pumpable.
So p=24: shortest b-string that needs pumping is b^24 (=b^(3*2+18)). Split b^24 as x=epsilon, y=b^3, z=b^21. xy^i z = b^(3i+21) = b^(3(i+1)+18) in L for i >= 0 (giving b^21, b^24,...). For i=0: b^21 = b^(3*1+18) in L. Good! For a-strings: a^(2m) with 2m >= 24, m >= 12. Split y=a^2, rest is even -- works. So p=24 works.
Verify p = 24: With p=24: strings in L of length >= 24 are: a^(2m) for 2m >= 24 (m >= 12), and b^(3n+18) for 3n+18 >= 24 (n >= 2), i.e., b^24, b^27,...
For a^(2m), m >= 12: split x=epsilon, y=a^2, z=a^(2m-2). |xy|=2<=24, |y|=2. xy^i z = a^(2+2i+2m-2) = a^(2m+2i-2)... let me use y=a^2 at the start. Actually more simply: for a^(2m) pick y = a^2 at any position; xy^i z = a^(2m-2+2i) = a^(2(m-1+i)) is even and >= 0 for i >= 0. In L. Good.
For b^(3n+18), n >= 2: split x=epsilon, y=b^3, z=b^(3n+15). xy^i z = b^(3i + 3n+15) = b^(3(i+n-1)+18). For i=0: b^(3(n-1)+18) with n-1 >= 1, so this is in L. For all i >= 0: 3(i+n-1)+18 with i+n-1 >= n-1 >= 1 >= 0. In L. Good.
So p=24 is valid.