GATE CS 2019 Set 1 — Question 25

The Pumping Lemma for regular languages states that there exists a constant $p$ (pumping length) such that any string $s \in L$ with $|s| \ge p$ can be split into $xyz$ satisfying specific conditions, primarily that $xy^iz \in L$ for all $i \ge 0$.The language $L$ consists of strings of 'a's with lengths in arithmetic progression $2, 5, 8, \dots$ (period 3) and strings of 'b's with lengths $10, 22, 34, \dots$ (period 12).If we choose a pumping length $p$, it must be sufficient to pump any string in $L$ of length $\ge p$.
Consider the string $b^{10}$. It is in $L$. If $p=9$, we must be able to pump $b^{10}$. Since the string consists only of 'b's, the pumped part $y$ must consist of 'b's. The lengths of 'b' strings in $L$ are separated by 12. Thus, $|y|$ must be a multiple of 12 to stay in $L$. However, the condition $|xy| \le p$ implies $|y| \le 9$. There is no multiple of 12 in the range $[1, 9]$. Thus, 9 cannot be a pumping length. Similarly, 3 and 5 are too small.If $p=24$, any string in $L$ with length $\ge 24$ will have length $\ge$ the period of its respective component (3 for 'a', 12 for 'b'). Specifically, the number of states in the minimal DFA for $L$ would be roughly $3 + 12 + 2 = 17$ (approx). Since $24 \ge$ number of states, it is a valid pumping length.