# Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$

To understand the Pumping Lemma, I'm going to prove that the language $$L = \{0^n1^m0^n | n,m \geq0\}$$ is not regular. I choose string $$w = 0^{p/2}1^{p/2}0^{p/2}$$, for any even number $$p$$. Clearly $$|w| > p$$. I use the following decomposition

• $$x = 0^{p/2}$$
• $$y = 1^{p/2}$$
• $$z = 0^{p/2}$$

Clearly for any $$i$$, $$xy^iz \in L$$, because the number of $$1$$s is not important and it doesn't lead to a contradiction. I think there is something I didn't understand about the Lemma. I appreciated it if you let me know why while $$L$$ is not a regular language, but my decomposition didn't lead to non-regularity.

As another example, consider language $$L_1 = \{0 ^{3n} | n \geq 0\}$$. This language is clearly regular. I choose $$w = 000000$$, for $$p=3,$$ $$x=0, y=00, z=000$$. It is clear pumping $$y$$ in for $$i=2$$ $$xy^iz = 00000000 \notin L_1$$ while the language is regular. Why I could find a decomposition that shows it is non-regular while the language is regular?

• @Steven This is exact;y my problem. I appreciate it if you post this hint and clarify the prblem of my proof Commented Apr 24, 2023 at 13:14

To show that a language $$L$$ is not regular you need to argue that the pumping lemma does not hold. That is, you want to show that for every $$p$$, there exists some word $$w$$ such that, for every decomposition of $$w$$ as $$xyz$$ with $$|xy| \le p$$ and $$|y| \ge i$$, there exists some $$i \ge 0$$ such that $$xy^i z \not\in L$$.

The quantifiers and their order are critical. What you can do is choose $$w$$ as a function of $$p$$. You don't get to choose a specific decomposition $$xyz$$, so you want to pick a $$w$$ that will make easy to argue about all possible decompositions.

In you first example $$w = 0^{p/2} 1^{p/2} 0^{p/2}$$ is not a great choice since there is a way to write $$w$$ as $$xyz$$ such tat $$xy^i \in L$$ for all $$i \ge 0$$. However, this doesn't tell you anything about the (non-)regularity of $$L$$ since there might be other choices of $$w$$.

Pick, for example, $$w = 0^p 1^p 0^p$$. Then, all decompositions are of the form $$x= 0^{a}$$, $$y = 0^{b}$$, $$z=0^{p-a-b}1^p 0^p$$, for some $$a \ge 0$$, $$b \ge 1$$ with $$a+b \le p$$. Therefore $$xy^iz = 0^{p + (i-1)b} 1^p 0^p$$. You can then pick $$i=0$$ (this is just an example, any $$i\neq 1$$ works in this case) to get $$xy^0z = 0^{p-b}1^p0^p \not\in L$$.

Conversely, if a language $$L$$ is regular, then there is some $$p$$, such that all $$w \in L$$ with $$|w|\ge p$$ admit some decomposition $$w=xyz$$ such that $$xy^iz \in L$$ for all $$i$$.

You don't get to choose the decomposition (as you have done) and, in general, you don't get to choose $$p$$. The pumping lemma only tells you that some $$p$$ exists.

Now, in your particular case it happens that the pumping length $$p$$ of $$L$$ is actually $$3$$ (this can be shown by arguing that a DFA with $$3$$ states can recognize $$L$$, you can't just blindly fix a value). Your example doesn't work because you picked the wrong decomposition of $$w=000000$$. Here is a decomposition that satisfies the pumping lemma: $$x= \varepsilon$$, $$y=000$$, $$z=000$$.