The GATE Grind

GATE 2019 CS – Question 25

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

For $\Sigma=\{a,b\}$, let us consider the regular language $L=\{x\mid x=a^{2+3k}\text{ or }x=b^{10+12k},\ k\ge0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$?

  1. 3
  2. 5
  3. 9
  4. 24

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 24

Explanation

A pumping length $p$ must be such that every string of length at least $p$ in $L$ can be pumped. The strings $a^{2+3k}$ can be pumped with a cycle of length 3 and the strings $b^{10+12k}$ with a cycle of length 12, but the shortest $b$-string has length 10, so any valid pumping length must exceed 10 and be a multiple that accommodates the cycle of 12. Among the options, only 24 works.