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

$$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?

migrated from stackoverflow.comAug 25 '12 at 10:59

This question came from our site for professional and enthusiast programmers.

• Now let me ask you this, why are you choosing a pumping length? In my proofs I always just chose a word at least as long as the pumping length, but represented in terms of it, for example a^2p with p being the pumping length. – Platinum Azure Aug 24 '12 at 5:21
• More relevantly, it's much easier to construct a finite automaton or regular expression to prove regularity... To prove regularity with the pumping lemma, you must show that no word fails the pumping ability and that's a lot harder than finding one that does fail for non-regular languages. – Platinum Azure Aug 24 '12 at 5:24
• thnx for help. Wat u r saying is to take p=4 and therefore w=aaaaaaaa, it will give same results. Correct me if im wrong – Raj Aug 24 '12 at 5:25
• No, I'm saying don't give p a value. The pumping lemma states that there exists a value for p, such that strings longer than it in length can be pumped. You're choosing the wrong value for p, and more importantly you can't just assign a value to it in the first place. In my answer I suggested a simpler way to prove regularity. – Platinum Azure Aug 24 '12 at 5:30
• Careful, the pumping lemma says that if the language is regular, then it can be pumped. But the converse isn't true. – vonbrand Jan 18 '13 at 12:56

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.

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.

• The pumping lemma is useful for proving non-regularity (though again, it's not foolproof). But it's definitely hard- I have awful memories of Theory of Computing class from those lectures! Good luck. – Platinum Azure Aug 24 '12 at 5:41
• Although Raj doesn't prove that 6 (not 4) is a valid pumping length, it is. The real problem in the proof is elsewhere: you must check all decompositions, not just one. – Gilles Aug 25 '12 at 12:36