# Pumping lemma for 0^n and n>0

When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following:

$S = 0^p$
$x = \varepsilon$
$y = 0^p$
$z = \varepsilon$

so $S = xyz = (\varepsilon)0^p(\varepsilon)$

For $x y^i z$ if i choose $i = 0$ (pumping down) i get $S = \varepsilon$, which is not an element of $L$.

Therefore according to the pumping lemma this language is not regular. But since I am able to draw a DFA for $L$, I know it is regular.

I would like to know what rules I am violating by trying to apply the pumping lemma to $L$ in this manner.

The pumping lemma says that you can split the word into $xyz$. It doesn't say that every such split works. For instance, if you take $|x|=1$ in your example, the pumping works up and down. This would be a "correct split" that makes the pumping lemma hold.

As a reference, recall the definition of the pumping language for regular languages (from Wikipedia):

Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:

1. $|y| \ge 1$
2. $|xy| \le p$ and
3. for all $i \ge 0$, $xy^iz \in L$.
$y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).
• Thank you for the quick reply. Did you reformat the post using Latex? Oct 29 '14 at 4:30
• Yes, see a short guide in meta.math.stackexchange.com/questions/5020/… Oct 29 '14 at 14:16
• But wait -- if n = 1 in the op's L, you can't take |x| = 1, because |y| has to be >= 1. That leaves $\varepsilon$ for x, which is |x|=0. How can it be pumped down then? May 20 at 19:05
• Ahh, all words longer than p can be pumped, so in the case we need to omit n=1 and start at n=2 cs.stackexchange.com/a/1848/24350 May 20 at 19:29