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

This question already has an answer here:

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?

marked as duplicate by Apass.Jack, Evil, Yuval Filmus formal-languages StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 5 at 12:36

• Please read the pumping lemma very slowly and carefully. Please the examples in course material very slowly. – Apass.Jack Mar 22 at 18:06
• $010000=xyz$ where $x=01$, $y=0$ and $z=000$. We have $xy^iz\in L$ for all $i$. – Apass.Jack Mar 22 at 18:08
• You can read this answer to appreciate the full intricacy of the pumping lemma. – Apass.Jack Mar 22 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 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 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 at 12:36