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

652 Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST 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").