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:$\lvert y \rvert \ge 1$$\lvert xy \rvert \le p$$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.
What's wrong with my pumping lemma proof?
formal languages;regular languages;proof techniques;pumping lemma