1
$\begingroup$

I am trying to prove that the follow language is not regular

L = {w ∈ {0, 1}∗ | the number of 1s in w is one more than the number of 0s}

My approach was to prove that it is regular and prove by contraction. So far I have:

p = pumping length

S = 0p1p and I could use 00111 string as an example I supposed. Am I going about this the right way? How could I go forward? I am new to pumping length.

$\endgroup$
1
$\begingroup$

Suppose that $L$ is regular. Then the pumping lemma says that there is a pumping length, $p$, such that if $s\in L$, and $|s|\ge p$, then $s$ can be decomposed as $s=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$. To use this to get a contradiction, you need to start with some $s\in L$ that is at least $p$ in length.

I would start with $s=0^p1^{p+1}$: it has one more $1$ than it has $0$s, so it’s in $L$, and it’s certainly at least $p$ characters long. Moreover, the pumping lemma tells you that it can be decomposed as $xyz$ in such a way that $|xy|\le p$, which means that $xy$ lies entirely within the string of $p$ $0$s. Thus, there are non-negative integers $r$ and $s$ such that $x=0^r$, $y=0^s$, $r+s\le p$, and $s\ge 1$. Now the pumping lemma says that $xy^kz\in L$ for each $k\ge 0$; we’d like to get a contradiction by showing that this simply isn’t true for this particular $s$. So what is $xy^kz$? If $xy=0^{r+s}$, that leaves $p-(r+s)=p-r-s$ $0$s at the beginning of $z$ together with all $p+1$ of the $1$s, so $z=0^{p-r-s}1^{p+1}$, and

$$xy^kz=0^r(0^s)^k0^{p-r-s}1^{p+1}=0^{r+ks+p-r-s}1^{p+1}=0^{p+(k-1)s}1^{p+1}\;.$$

It’s not hard now to find values of $k$ for which $xy^kz\notin L$, and doing that proves that $L$ could not have been regular after all: it doesn’t satisfy the conclusion of the pumping lemma.

$\endgroup$

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.