GATE CS 2019 Q15 — Pumping Lemma

According to the Pumping Lemma for regular languages, if $L$ is regular, there exists a pumping length $p$ such that any string $s \in L$ with $|s| \ge p$ can be split into $s = xyz$ satisfying:

1. $|xy| \le p$
2. $|y| \ge 1$
3. $xy^i z \in L$ for all $i \ge 0$

Let us analyze the given language $L = L_1 \cup L_2$, where $L_1 = \{a^{2+3k} \mid k \ge 0\}$ and $L_2 = \{b^{10+12k} \mid k \ge 0\}$.

Testing options $p = 3, 5, 9$:

Consider the string $s = b^{10} \in L_2 \subseteq L$. Since $|s| = 10 \ge p$ for $p \in \{3, 5, 9\}$, we must be able to pump it. Let $y = b^m$ where $1 \le m \le p$.

• For $i = 0$, the pumped string is $xy^0z = b^{10-m}$.
• Since $1 \le m \le p < 10$, the length of $xy^0z$ lies in the range $[10-p, 9]$.
• However, the minimum length of any string of $b$'s in $L$ is $10$. Thus, $xy^0z \notin L$.

Hence, $3, 5,$ and $9$ cannot be pumping lengths.

Testing option $p = 24$:

• Case 1: For $s = a^{2+3k} \in L_1$ with $|s| \ge 24$, we can choose $y = a^3$ within the prefix of length $24$. Pumping $y$ changes the length by multiples of $3$, keeping the pumped string in $L_1$.
• Case 2: For $s = b^{10+12k} \in L_2$ with $|s| \ge 24$ (which implies $|s| \ge 34$), we can choose $y = b^{12}$ within the prefix of length $24$. Pumping $y$ changes the length by multiples of $12$, keeping the pumped string in $L_2$.

Thus, $24$ is a valid pumping length for $L$.