# Choosing $x$, $y$, $z$ parts in a pumping lemma $w$ string

I want to proof that $L = \left\{u0v \mid u, v \in \{0, 1\}^* \land \#_1(u) = \#_0(v) \right\}$ is not regular. But my understanding of the pumping lemma is somehow not bulletproof, so I'm not sure if I'm right in what I'm doing.

I chose $w$ to be $1^k00^k = xyz$, so $|w| \ge k$, which is correct I hope. Now I'm not really sure how to correctly choose what is $x,y$ in this string. Can $y$ be any part of $w$ (having in mind the condition $|xy| \le k$)? For example let's $x$ be equal to $1^m$, $y$ then will be $1^n$ and $z$ will be $00^{m+n}$ (where $m+n = k$). Then assuming that $xy^iz \in L$ for $i\ge0$, let $i$ be $0$. Then there is only a string $1^m00^{m+n}$ left, which is not from $L$. Is this proof correct? It makes sense in some way, but I can't say if all the steps I took were alright.

• I suppose $\#_1(u)$ means the number of $1$'s in $u$, and similarly for $\#_0(v)$. If so, then $1^m00^{m+n}$ would be in $L$, because it has the form $u0v$ with $u=1^m0^n$ and $v=0^m$, where $\#_1(u)=\#_0(v)=m$. – Andreas Blass Oct 24 '17 at 20:17

## 1 Answer

Inside any substring of length $>k$ you can find a pumpable substring. So taking that substring inside the $0$ part is OK. You should try to understand the pumping lemma, rather than just applying it, the idea is simple: if you go $k+1$ times to $k$ places, you have to go to the same place at some point (like bar hopping, the automaton is "place hopping").

• Hm, I probably didn't get any of what you say. Didn't you mean "inside any substring of length $< k$" (which would be $|xy| < k$ and the pumpable substring would be $y$ then)? But I placed it to the $1$ part, not $0$ - from my question: "$y$ will be $1^n$". If i'm right I think I understand the "pumping substring idea", although not sure what you meant by "$k+1$ times to $k$ places...". And then finally: is my demonstration proof correct? – T.Poe Oct 24 '17 at 18:31
• And to the "pumping substring" idea; I can find any substring of $w$ which fulfils all the PL conditions and then I find any $i$ for which the string doesn't belong to the original language $L$? – T.Poe Oct 24 '17 at 18:36
• @T.Poe: your proof is correct. The pumping lemma should be formulated like this: there exists $k$ ( the numbers of states of the automaton) so that for every $w$ string and every $w_1$ substring of $w$ of length $>k$, there exists a decomposition $w_1 = x y z$, with $1 \le |y|$( $\le p$) so that all the strings obtained from $w$ by replacing $y$ with powers of $y$ are in the same class of $w$ ( accepted or rejected). The pumping lemma is in general not stated in this form... – Orest Bucicovschi Oct 24 '17 at 18:44