We have to prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular.

Attempt: We assume that the language is regular. Thus it would satisfy the pumping lemma. Assume the pumping length to be $p$. Let us take the string would be length $p+1$ as $0 0^p 1^{p+1}$. Now we need to divide this string into three parts $xyz$ such that the pumping property does not hold. The pumping lemma restricts the size of $xy$ to be less than or equal to $p$. So the y part can comprise entirely of only $0$'s. If we pump the $y$ part we can end up with strings having more number of $0$'s than $1$'s. Is this correct with respect to the string that has been considered? What other strings can be used to show this?


First of all, your language definition seems vague. By "starting with a 0", it can mean two things. Either there is an extra 0 at the beginning of the string, followed by equal number of 0s and 1s, i.e number of 0's is greater than the number of 1's by 1, or it could also mean the string has an equal number of 0's and 1's, but starts with 0 instead of 1. Please define it clearly for the sake of clarity. I'm assuming your language definition to be the former, since you've mentioned in your attempt that you're taking the generic string to be $00^p1^{p+1}$, basically implying the string is of the form $0^n1^n$.

Secondly, the length of the string you've taken, $i.e$ - $|0 0^p 1^{p+1}| = 1+p+p+1 = 2p+2$, and not $p+1$.

Given that the string you have taken is of length 2p+2 which is definitely greater or equal to $p$ (the pumping length you have assumed in this case), your approach seems right. Although you can use the generic proof of proving that any language of the form $L = \{ a^nb^n : n ≥ 1 \}$ is not regular, in this case.

Regarding what other string you could take, You can basically take any string of the form $0^n 1^n$ (divide it however you want), i.e it should just satisfy the condition that there should be equal number of $0$'s and $1$'s, and start with zero.

The generic string $0^n 1^n$ works for the general proof. It is obviously longer than $n$. Considering $xyz = 0^n 1^n$, $|xy| ≤ n$, hence $y$ can only contain $0$'s, $y ≠ \epsilon$, $\implies$ y must contain at least one 0. Now $xy^0z \in L$ according to the pumping lemma, but this is a contradiction, as it would imply that it contains at least one $0$ less, but the same number of $1$s as in $0^n 1^n$. Hence, L is not regular.


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.