Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular

Question

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?

Answer 1

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.

Answer 2

Let us denote by $L_b$ the language of all words with equally many 0s and 1s, starting with $b \in \{0,1\}$. By symmetry, $L_0$ is regular iff $L_1$ is regular. Therefore, if $L_0$ is regular then so is $L_0 \cup L_1 \cup \{\epsilon\}$, which is the language of all words with equally many 0s and 1s. The latter is known to be non-regular, hence $L_0$ must be non-regular as well.

Answer 3

Use the pumping lemma, and note that you can select the string to be pumped (the pumping lemma states that all strings in the regular language at least $p$ long can be pumped).

Assume $L$ is regular, so it satisfies the pumping lemma, let $p$ be the constant of the lemma, which we know is at least 1. Select the string $0^p 1^p$, which certainly is in the language and longer than $p$, so by the lemma you can write it $x y z$ with $\lvert x y \rvert \le p$ (thus $x$, $y$ are all 0s) and $y \ne \epsilon$, but then $x y^0 z$ has less 0s than 1s, thus it isn't in $L$.

Answer 4

Let $L$ be your language. If it were regular, so would be its intersection with the regular language $0^*1^*$. But $$ L \cap 0^*1^* = \{0^n1^n \mid n > 0\} $$ is known to be non-regular. Thus $L$ is not regular.

Answer 5

Assume there is a state machine recognising L. Let $S_n$ be the state reached after processing n 0's, n ≥ 1. If n ≠ m then $S_n$ and $S_m$ are different states , because in state $S_n$ processing n 1's leads to an accepting state, but in state $S_m$ it doesn't.

Therefore the number of states is not finite. Therefore L is not regular.

(It's often quite easy to show that a language cannot be handled with any finite set of states. The pumping lemma is on the other hand is based on the fact that if a prefix of a string is longer than the number of states, then while processing the prefix you must have entered some state S twice. So you processed some y to go from S to S. But then by processing y a billion times, you would have gone from S to S a billion times, so the result must also be in the language. In the pumping lemma, p is the number of states plus 1, x is the string that took you from the starting state to S, y is the string that took you from S back to S, and z is the string that took you from S to an accepting state).

Answer 6

With the pumping lemma it helped me to practice the rules with a bunch of examples placed in the x, y, z colums, along with values for p. Keep in mind all words longer than 𝑝 can be pumped, and p >= 1.

For this scenario, p=1 isn't going to work because you'll pull out a 1 or a 0 into the y, then when you try to repeat the y in the xyz you'll break the "equal number of 0s and 1s" rule.

Next, try p=2 (but omit 01, because |01| = 2 and 2 is not less than p). We can pump 0110, 01011100 fine, because x is empty, y is 01, z is the rest. Pump down, removing y and we're ok. Pump up adding many y's we're ok. So far...

But not

0011

Why?

Split out the 00 into y, repeating y will give you more 0s than 1s. Split out the 01 in the y to keep 0s and 1s even when y repeats, but then you have have to put the first 0 in the x. Length of x is 1 + length of y is 2 = 3, which exceeds p (the pumping lemma rule |xy| <= p). 00001111 has the same result, p=3, p=4... all break the rules again.