# Confused about pumping lemma, What i'm missing? [duplicate]

When I apply pumping lemma on this language: $${L=\{010^n:n\ge0\}}$$ over the alphabet $${\Sigma =\{0,1\}}$$ I get that it is non-regular despite the fact that it is regular.

1. let $${n=4}$$, then $$w=010000$$
2. $$w=xyz$$ , $${ \mid xy\mid \leq n}$$ and $${\mid y\mid \geq 1}$$
3. $$x=0$$ , $$y=10$$ , $$z=000$$
4. let $$i =2$$
5. $$xy^2z = 01010000$$ $$\not\in L$$ so L is non-regular.

so, what I'm missing?

• Please read the pumping lemma very slowly and carefully. Please the examples in course material very slowly. – John L. Mar 22 '19 at 18:06
• $010000=xyz$ where $x=01$, $y=0$ and $z=000$. We have $xy^iz\in L$ for all $i$. – John L. Mar 22 '19 at 18:08
• You can read this answer to appreciate the full intricacy of the pumping lemma. – John L. Mar 22 '19 at 18:15

you can't claim to know how $$w$$ distributes.

you know that some $$w \geq n_0$$ exists, in such a way it can be denoted as

$$w=xyz$$

$$y \neq \epsilon$$

$$|xy|\leq n_0$$

and for every $$i>0: xy^iz \in L$$

your error is that you claimed you know the distribution of $$w$$ to $$x,y,z$$. Namely, you fixed $$y$$ to be $$10$$

The language of course can be pumped, since it's regular. But for any $$w = xyz, y$$ must be a word of only $$0$$, since $$1's$$ cannot be pumped.

• OK now i get it, you say that I should try all distribution of w to x,y,z. until I get one that belongs to Language. x=01 , y=0 , z=000 for example then I can say that "I can't prove that L is non-regular so I'll try building DFA to prove regularity" – Osama Samir Mar 22 '19 at 18:51
• DFA is indeed the way to go when you want to prove some language $L$ is regular. the pumping lemma only helps disproving regularity; in which case you must prove that any valid distribution of $w$ to $xyz$ cannot be pumped. – lox Mar 22 '19 at 19:26
• What does "$w \ge n_0$" mean? In fact, there exists $n_0$ for which every $w \in L$ of length at least $n_0$ can be "pumped". – Yuval Filmus Apr 5 '19 at 12:36