$L=\{w \in \{0,1,a\}^* | \#_0(w) = \#_1(w) \}$

We show that L is not regular by pumping lemma.

We choose w=$0^p 1^p a$

|w| = 2p+1

Now |xy| has to be $\leq p$

So x and y could only contain zeros. And $z=1^p a$

$xy^iz= 0^p 1^p a$

Now let i = 0

$xy^0z=0^{p-|y|} 1^p a$

Now hence $p-|y| \neq p$ this choice of i would lead to a word that is not in L. So we can not pump y and stay in the language.

So L is not regular.

I'm trying to learn the usage of the pumping lemma. Is my proof correct?

Any suggestions are welcome. Thanks!

  • $\begingroup$ "Now |xy| has to be ≤𝑝" what are x and y? $\endgroup$ – Jeffrey Aug 11 '20 at 21:19
  • $\begingroup$ Pumping lemma states that w has to be split into xyz. So x the first part y the second and z the last part of w. Do I have to mention this in every proof for it? $\endgroup$ – Rapiz Aug 11 '20 at 21:24
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Aug 12 '20 at 6:27
  • $\begingroup$ It's proof verification. I have asked for suggestions to improve my proof. $\endgroup$ – Rapiz Aug 12 '20 at 8:41

Use your freedom to pick a string to work with. The string $0^p 1^p$ is all around nicer.

Assume $L = \{ w \in \{0, 1, a\}^* \colon \#_0 w = \#_1 w \}$ is regular, so it satisfies the pumping lemma. Let $p$ be the constant of the lemma, we know $p \ge 1$. Pick $w = 0^p 1^p$, so $\lvert w \rvert = 2 p \ge p$, by the lemma there is a division $w = x y z$ with $\lvert x y \rvert \le p$ and $y \ne \varepsilon$ so that for all $k \ge 0$ the string $x y^k z$ belongs to $L$.

What does the above tell you about $x, y, z$? Can you derive a contradiction by picking e.g. $k = 0$? You finish it off.

  • $\begingroup$ I have done the same so far. $\endgroup$ – Rapiz Aug 12 '20 at 8:40

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.