I require assistance in proving this language as not regular

Question

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.

Answer 1

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