0
$\begingroup$

I just got my homework back after correction and I can't figure out why this questions was wrong.

I need to say if I can prove that the language ${L=\{w\in \{0,1\}|w}$ has more 0's than 1's} is not regular with a given string.

Both $0^p1^p$ and $0^{p+1}1^p$ were options and I said both could be used, but the correct answer was that only $0^{p+1}1^p$ could be used?

I thought that if $s=0^{p}1^p=xyz$ then $xy^0z$ would make it so that there would be less than $p$ zeros since $y>0$.

Is my logic wrong or was it a bad correction? Thanks!

$\endgroup$
0
$\begingroup$

The string $0^p1^p$ is not an element of the language $L$ (it does not have more $0$s and $1$s). The pumping lemma only applies to strings that are actually in the language!

$\endgroup$
  • $\begingroup$ These silly mistakes get me every time. Thanks! $\endgroup$ – AxG Nov 8 '17 at 3:55

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.