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 Feb 12 at 11:46

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$ – Arun Kumar Singh Feb 9 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$ – Kuldeep Singh Feb 12 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 Feb 12 at 18:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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