6
$\begingroup$

The language $L = \{0^{2n} \space |\space n \ge 0 \}$ is obviously regular – for example, it matches the regular expression $(00)^*$. But the following pumping lemma argument seems to show it's not regular. What's gone wrong?

I've found a way of splitting an input $s$ as $xyz$ satisfying the requirements of the pumping lemma but it's not true that $xy^iz\in L$ for all $i$. Doesn't that mean the language isn't regular?

In more detail, the pumping lemma for regular languages says that, if a language $L$ is regular, there exists pumping length $p \ge 1$ such that any string $s\in L$ with $|s|> p$ can be written as $s = xyz$ such that:

  1. $\lvert y \rvert \ge 1$
  2. $\lvert xy \rvert \le p$
  3. $xy^iz\in L$ for all $i \ge 0$.

So, let's take $s = 0^{2p}$ and write it as $s=\epsilon\, 0 \, 0^{2p-1}$ (i.e., $x = \epsilon$, $y = 0$, $z = 0^{2p-1}$). This satisfies 1. and 2. But, taking $i=0$, we get $xy^iz = \epsilon\, 0^0\,0^{2p-1} = 0^{2p-1}$, which isn't in $L$ because its length is odd. So it looks like the language isn't regular after all.


This is intended as a reference question illustrating a common mistake in the use of the pumping lemma for regular langauges. Thanks to Ariel for spotting the issue in the original version of the question.

$\endgroup$
  • 4
    $\begingroup$ The pumping lemma states that for words greater than some length $p$ there exists such decomposition. You have shown a specific decomposition that does not work, but take any word of length greater than 2 and $y=0^2$. (God have mercy on my soul for responding) $\endgroup$ – Ariel Aug 3 '15 at 20:15
  • $\begingroup$ There are pretty good guides in previous posts, e.g., cs.stackexchange.com/questions/1031/… $\endgroup$ – Ran G. Aug 3 '15 at 22:25
  • 1
    $\begingroup$ @RanG. That post is an excellent guide on how to prove that a language isn't regular but we do seem to get somewhat frequent questions where somebody has tried to apply the pumping lemma and made exactly this mistake. I think it's more helpful to point out what the mistake is in such a proof (e.g., by marking as a dupe of this question) than it is to say, "Here's how to do it properly; you figure out waht the difference between your approach and the correct one is." $\endgroup$ – David Richerby Aug 3 '15 at 22:28
  • 1
    $\begingroup$ @DavidRicherby you are right, this question is not about showing non-regularity using pumping. The most common mis-use of the lemma is misunderstanding the quantifiers, and the guide at the question I mentioned tries to address that issue (e.g., by writing in bold letters: all ways to partition it, etc.) $\endgroup$ – Ran G. Aug 3 '15 at 22:32
  • $\begingroup$ The lemma ensures there is some splitting that works if the language is regular. To prove it is not regular, you have to prove that no splitting works. $\endgroup$ – vonbrand Aug 4 '15 at 1:25
5
$\begingroup$

The problem is in the quantifiers. The pumping lemma says that any string $s$ with $|s|\geq p$ can be written as $xyz$ such that the three properties hold. It doesn't say that every way of writing it as $xyz$ that makes the first two properties hold also makes the third one hold.

For the language $\{0^{2n}\mid n\geq 0\}$, we proceed as follows. First, note that we must have $p\geq 2$, since if $p=1$, we're forced to take $x=\epsilon$, $y=0$, $z=0^{2p-1}$ and you already showed in the question that this doesn't work. So, with $p\geq 2$, we can write $s = 0^{2p}$ as $s=\epsilon\,00\,0^{2(p-1)}$ ($x=\epsilon$, $y=00$, $z=0^{2(p-1)}$). We have $|\epsilon00| \leq p$, $|00|>1$ and $(00)^i\,0^{2(p-1)}\in L$ for all $i\geq 0$. Thus, there exists some way of decomposing the string as $xyz$ that satisfies all the properties, even though the first decomposition you thought of didn't work.

To show that a language isn't regular, you need to show that every decomposition into $xyz$ that satisfies the first two properties fails to satisfy the third one. It's not enough to just show that one decomposition doesn't work.

To understand why the pumping lemma is the way it is, it helps to think about the proof. If a language is regular, it is accepted by some DFA. That DFA has some number of states: call it $p$. By the pigeonhole principle, whenever that DFA reads a string longer than $p$, it must visit some state twice: say state $q$. Now, $x$ is the part of the input read upto (and including) the first visit to $q$, $y$ is the part read after the first visit and upto and including the second (which must be at least one character) and $z$ is the rest. But now you can see that $xz$ must be accepted: $x$ takes you from the start state to $q$ and $z$ takes you from $q$ to an accepting state. Likewise, $xy^iz$ must be accepted for any positive $i$, since each repetition of $y$ takes you from $q$ back to $q$. Note that the decomposition of the input into $x$, $y$ and $z$ is entirely determined by the automaton which is, in turn, determined (but not uniquely) by the language. So you don't get to choose the decomposition: if the langauge is regular, some decomposition exists; to show that a language is not regular, you must show that every decomposition fails.

$\endgroup$
  • $\begingroup$ This is a good explanation but I'm getting lost after reading cs.stackexchange.com/a/1051/10511. Take a look at item 4. He is taking about considering all the way to split the string into 3 substrings. The way I read it is that it is that I should be able to pump it every way I split the string assuming I'm given a regular language. So where is the error? This really bugs me that I don't understand it. To the point that I can't get normal sleep at night. $\endgroup$ – flashburn Aug 4 '15 at 3:31
  • $\begingroup$ @flashburn If it's supposed to be non-regular, no splitting can work. Here we find one that works, so we can't show it's non-regular using this lemma. $\endgroup$ – Raphael Aug 4 '15 at 6:27
  • $\begingroup$ @flashburn I've added an explanation about why the pumping lemma is true, which might help you to understand, by showing where the requirements of the lemma come from. $\endgroup$ – David Richerby Aug 4 '15 at 9:40
  • 1
    $\begingroup$ @flashburn Also, if your studies are stressing you out so much you can't sleep properly, you should have a chat with your university's counselling service. The pumping lemma's kind of important but your health and wellbeing are much more important. $\endgroup$ – David Richerby Aug 4 '15 at 9:42
  • 2
    $\begingroup$ Not to mention that proper sleep, nutrition and exercise will make your mind work much better, @flashburn. See also here. $\endgroup$ – Raphael Aug 4 '15 at 9:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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