The following question on the theory of computation is GATE 2019 CS question 24:

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

(A) 3$\quad$(B) 5$\quad$(C) 9$\quad$(D) 24

My Attempt

I tired to solve like this. I divide the minimum string possible into $x(y^i)z$ that is $a^2$ so getting i value $2$ but option not available.

Then I take second minimum $a^5$ i.e., taking $x=\epsilon$ and $y=a^5$ and $z=\epsilon$.

I am getting $i=5$. So is it correct answer??

  • 1
    $\begingroup$ If any of those numbers work, any larger number can be "the" pumping length. So 2) is a safe bet. $\endgroup$
    – Raphael
    Commented Feb 12, 2019 at 11:46

1 Answer 1


I am getting i=5. So is it correct answer?

I am afraid I could not understand your argument and conclusion clearly.

Anyway, can you check if you are able to pump $a^2, a^5, b^{10}, b^{22}$ using the pumping length of your choice?

Here are a few results stated in the form of exercises that you can prove and use to solve the problem in the question and beyond.

Assume $L$ is an arbitrary regular language.
Exercise 1. Show that there exists $p_0=p_0(L)\in \Bbb N^+$ such that $p\in\Bbb N$ is a pumping length for $L$ iff $p\ge p_0$.
We call $p_0$ the minimum pumping length of $L$.

Exercise 2. Let $L_{m,n}=\{a^m, a^{m+n}, a^{m+2n}, \cdots\}$ for $m,n\in\Bbb N$, $0<n$. Show that $p_0(L_{m,n})=m+1$.

Exercise 3. Let $L_1, L_2$ are two regular languages. Show that $p_0(L_1\cup L_2)\le\max(p_0(L_1), p_0(L_2))$

Exercise 4. Let $L_1, L_2$ are two regular languages over disjoint alphabets that do not contain the empty word. Show that $p_0(L_1\cup L_2)=\max(p_0(L_1), p_0(L_2))$

Exercise 5. Show that 11 is the minimum pumping length of $\{x\mid x=a^{2+3k} \text{ or } x=b^{10+12k},\ k\ge0\}$.

  • 1
    $\begingroup$ I got your point. The minimum pumping length will be 11 for the above language. And possible pumping length 'p' can be any length greater than or equal to minimum pumping length. $\endgroup$ Commented Feb 9, 2019 at 6:56
  • $\begingroup$ Apass.jack Its should be: Exercise 3. p0(L1∪L2)>=max(p0(L1),p1(L2)) Correct me if I'm wrong $\endgroup$ Commented Feb 12, 2019 at 10:31
  • 1
    $\begingroup$ @KuldeepSingh $\geq$ is certainly not true. Consider any regular language with pumping length > 1 and its complement; the pumping length of their union is 1 < max(...). $\endgroup$
    – Raphael
    Commented Feb 12, 2019 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.