# Proving that language $L = \{ a^{2n}: n \geq 1\}$ is regular

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?

• @ArghyaChakraborty why can't I choose n = 3 , isn't it arbitrary ? – Sigma Aug 7 '17 at 4:55
• "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. – Raphael Aug 7 '17 at 5:44
• – Raphael Aug 7 '17 at 5:45
• @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. – User Not Found Aug 7 '17 at 7:55
• Please check your assignment. Do you mean $\{ a^{2^n} \mid n\ge 1\}$? – Hendrik Jan Aug 7 '17 at 9:10

## 2 Answers

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.