Pumping Lemma for regular language for $a^n$ where $n$ is even fails

Question

$$L=\{a^n \mid \text{\(n\) is even}\}$$

This is regular but fails in the pumping Lemma.

Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even). Let $w=xyz$, $x=a$, $y=aaa$. We have $|y|>0$ and $|xy| \le m$.

Let $w_i=xy^iz$. For $i=2$, $w_2=xy^2z=aaaaaaaaa$. $|w_2|=9$ therefore it is not regular.

Where am I going wrong?

Answer 1

The pumping lemma states that:
there exists a pumping length $p$
such that for any word $w \in L$ of length $|w| \ge p$,
there exists a decomposition $w = xyz$
meeting certain properties.

There are two errors in your proof. The first is that the lemma states that there exists a pumping length $p$ but doesn't say how to compute it; you assume without proof that $6$ is a valid pumping length. This makes your proof incomplete, but it is not actually wrong: the pumping length can be anything larger than the number of nodes in the smallest finite automaton that recognizes the language, and this language can be recognized by an automaton with just two states, so any $p \ge 2$ is ok.

The fatal mistake is that you don't get the choice of the decomposition. There has to be some decomposition $w = xyz$ such that $\forall i, xy^iz \in L$. The one you picked doesn't work. In order to prove that the language isn't regular, you'd need to prove that no decomposition works. But there is a decomposition that works: take $x = aa$, $y = aa$, $z = aa$ (or any decomposition where $|y|$ is even).

You might have gotten confused with what happens when proving that a language is not regular. When proving the negation, the quantifiers are reversed: to prove that a language is not regular using the pumping lemma, we usually assume that the pumping lemma holds, so we assume the pumping lemma, and in particular we assume that for any sufficiently large word, there exists a decomposition meeting the properties, and we deduce a contradiction from that. Here, you're trying to deduce that the pumping lemma holds.

Answer 2

The simple answer is you're using the wrong approach. It's much easier to construct a regular expression or finite automation to prove that a language is regular.

This language is expressible using the following regular expression:

(aa)*

I think your issue is your assumption that the pumping length is 4. You can't just choose a pumping length- the lemma only says that for a regular language, there must exist one and only one pumping length, but the lemma does not help us guess what it is, nor do we need to know when disproving regularity. For proving regularity, I wouldn't use the pumping lemma at all because it is sometimes possible for a non-regular language to be pumped. Use a finite automaton or regular expression to prove regularity.