I was asked to prove that language described by $$ L =\{ a^{2n}: n\ge1\}$$ is regular using pumping lemma. Pumping Lemma states that for regular language we can break down language described by language into $xyz$ where pumping length $p \ge 1$ such that

  1. $|y|>0$
  2. $|x.y| \le p$
  3. $x.y^{i}.z$ is in L for $i \ge 0$

taking pumping length $n = 3$ , my language becomes $L = \{ aaaaaa\}$ and then let $$x = aaa$$ $$y = aa$$ $$z= a$$

clearly this violates condition 2 because $|xy| > p$ where $p=3$ and it also violates condition 3 for many values of $i$ thus this language cannot be regular but in the question I was asked to prove it to be regular, am I missing something?

  • $\begingroup$ @ArghyaChakraborty why can't I choose n = 3 , isn't it arbitrary ? $\endgroup$
    – Sigma
    Commented Aug 7, 2017 at 4:55
  • 4
    $\begingroup$ "I was asked to prove that [a language] is regular using pumping lemma." -- that's unlikely, since it's impossible. The pumping lemma can't be used in that way. $\endgroup$
    – Raphael
    Commented Aug 7, 2017 at 5:44
  • $\begingroup$ Duplicate? $\endgroup$
    – Raphael
    Commented Aug 7, 2017 at 5:45
  • $\begingroup$ @Sigma Forget my last comment. I was out of my mind. Anyways while proving not regular you have to prove for all $n$'s not just $n=5$ or something. And as the answer states, you can't use pumping lemma to prove language is regular. $\endgroup$ Commented Aug 7, 2017 at 7:55
  • $\begingroup$ Please check your assignment. Do you mean $\{ a^{2^n} \mid n\ge 1\}$? $\endgroup$ Commented Aug 7, 2017 at 9:10

2 Answers 2


The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \geq 0$.

Your language satisfies the pumping lemma, with $p = 3$ (as it must, since the minimal DFA contains 3 states). Indeed, let $w \in L$ be a word of length at least 3, so that $w = a^{2n}$ for some $n \geq 2$. Then $w$ can be decomposed as follows: $w = xyz$, where $x = \epsilon$, $y = a^2$, $z = a^{2n-2}$. Note that $|xy| = 2 \leq p$, $|y| = 2 \geq 1$, and for all $i \geq 0$, $xy^iz = a^{2n-2+2i} = a^{2(n-1+i)} \in L$ since $n \geq 2$.

The pumping lemma states that every long enough word $w \in L$ has some decomposition $w = xyz$ satisfying the requirements in the lemma. It doesn't claim that all decompositions satisfy the requirements.


Your language is regular. It is a set of even length $a$s expressed by the regular expression $r=aa(aa)^*$. The pumping lemma is used usually to prove that a language is not regular.


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.