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?

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


$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.

| cite | improve this answer | |
  • $\begingroup$ 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" $\endgroup$ – Osama Samir Mar 22 '19 at 18:51
  • 1
    $\begingroup$ 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. $\endgroup$ – lox Mar 22 '19 at 19:26
  • $\begingroup$ 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". $\endgroup$ – Yuval Filmus Apr 5 '19 at 12:36

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