# I require assistance in proving this language as not regular

I'm trying to prove that L = {$$0^n1^m0^n | m,n >= 1$$} in NOT regular but I am struggling with the demostration process.

I know the conditions are that:

• $$|y| > 0$$; $$'y'$$ can't be empty
• $$|xy| <= p$$(word/string length)
• for all $$i$$ > 0, $$xy^iz$$ must be in L

Lets choose the string $$s = 0^p10^p$$.

The first condition states that: $$y = 0^k$$ for $$k > 0$$

Being $$x$$ and $$y$$ composed of zeros such that complies with the second condition.

At $$i = 0$$, the string should be in L, thus $$xy^0z = xz = 0^{p-k}10^p$$ but $$y$$ can't be empty, right?

From now on, I get lost in the demostration and require help to properly prove it is not regular.

• If $p$ is the pumping length, then splitting the string $w=0^p10^p$ as per the pumping lemma must have $y \in 0^+$, and thus $z$ must be a finite suffix of the form $0^*10^p$. But then $w_i = xy^iz$ has a longer $0$-prefix than $0$-suffix when $i \geq 2$, creating a contradiction as all $w_i$ are supposed to be in $L$. Mar 28 at 21:16

First of all, the empty pump matters (in fact, sometimes the empty pump, e.g. the case $$i=0$$ is the simplest way to prove the non-regularity). Thus, the third condition is actually "for all $$i\geq 0$$ $$x y^i z\in L$$". The condition "$$y$$ can't be empty" is not about the iterations number (e.g. the string $$y^i$$), it states that the word $$y$$ itself is not empty. Otherwise, every language is trivially pumped if we choose $$y=\varepsilon$$ and the lemma is meaningless.
Thus, your proof is correct, using the empty pump. If you do not like the case $$i=0$$, you may choose $$i=2$$ and get another word $$0^{p+k}10^p\notin L$$, but imo your choice is nice enough.
The only imprecise part is about the order of the applications of 1st and 2nd conditions. If you do not apply the condition $$|xy|\leq p$$ to the word $$0^p 1 0^p$$, you cannot know in advance that $$y$$ consists of zeros. There are many non-empty subwords of $$0^p 1 0^p$$ containing also $$1$$. The condition $$|y|>0$$ determines that $$y=0^{k}$$, $$k>0$$ only after the second condition determines that $$y\in 0^*$$.
• @BadProgrammer I cannot see from the description of your language that the number of 1 and 0 must be equal or unequal. The only condition is that the number of zeros before 1 is the same as the number of zeros after 1. Thus, $0^{p+i*k}10^p$ is not in $L$ for all $i\neq 0$ (e.g., for all $y^j$, where $j\neq 1$). The pump throws us out of the language, and since all regular languages can be pumped, this language is not regular. Mar 28 at 21:53