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

$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

All Regular and Context-Free Languages, Pumping Lemma questions →