GATE 2019 CS – Question 25
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$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (D) 24
Explanation
$L=\{a^{2+3k}\}\cup\{b^{10+12k}\}$ is regular, so it has some pumping length. A number $p$ is a valid pumping length iff **every** string $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with $|xy|\le p$, $|y|\ge1$ and $xy^iz\in L$ for all $i\ge0$.
**The $a$-strings.** $a^{2+3k}$ can be pumped by taking $y=aaa$ (length 3): adding or removing blocks of three $a$'s keeps the length of the form $2+3k$ (as long as the length stays $\ge2$). So these strings are no problem once $p\ge3$.
**The $b$-strings.** $b^{10+12k}$ can only be pumped by a block whose length is a multiple of 12, and the smallest allowed block is $y=b^{12}$. For $y$ to fit inside the first $p$ symbols we need $p\ge12$ (if the string is longer than $p$). In addition, the string $b^{10}$ itself cannot be pumped at all: removing symbols leaves fewer than 10 $b$'s, and adding a block of length $\le10$ never gives a multiple of 12. So $b^{10}$ must be shorter than $p$, i.e. $p>10$.
Together: $p\ge12$. Of the options 3, 5, 9, 24, only **24** satisfies this.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2017 CS (CS1) Q48
- GATE 2014 CS (CS1) Q25
- GATE 2014 CS (CS2) Q25
- GATE 2014 CS (CS2) Q46
- GATE 2016 CS (CS2) Q27
- GATE 2016 CS (CS2) Q28
All Regular and Context-Free Languages, Pumping Lemma questions →