2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Andreas Blass Oct 24 '17 at 20:17
0
$\begingroup$

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").

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – T.Poe Oct 24 '17 at 18:31
  • $\begingroup$ 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$? $\endgroup$ – T.Poe Oct 24 '17 at 18:36
  • $\begingroup$ @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... $\endgroup$ – Orest Bucicovschi Oct 24 '17 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.