Show bit strings with count(1s) = count(0s) isn't regular

Question

Let L be the language consisting of strings over alphabet {0,1} that contain an equal number of 1s and 0s.

For example:

000111
10010011
10
1010101010

How can you show that L isn't a regular language?

Answer 1

I think you can use the exact same argument that is used to show that {0^n 1^n: n > 0} is not regular, since you are free to choose the string that will contradict the pumping lemma.

Assume L is regular. So it must satisfy the pumping lemma for some integer n (the pumping length). Take the string S=0^n 1^n, which belongs to L. According to the lemma, it can be split as S=xyz with |xy| <= n, |y|>0, and x y^i z belonging to L, for all i>=0. Observe that y must consist of zeros only. Now pump y, and you are only adding zeros to the string, which no longer belongs to L. So you have a contradiction. So L is not regular.

Answer 2

I don't know about a formal proof, but the intuition is that you cannot construct a DFA to recognize this language (consider that it would require an unobounded number of states to keep track of strings of the form 111...111000...000 or similar).

Answer 3

The formal proof can be given using the pumping lemma for regular languages as follows:

Suppose the language is regular. So it must satisfy the pumping lemma for a const integer p. Let s be any string with equal number of 0s and 1s. Then s can be divided into 3 parts x,y,z such that |xy|<=p, |y|>0, then x(y^i)z, where i>=0should also belong to L.

Let me divide the string as follows:

• y is a part of string which has unequal number of 0s and 1s.
• x could be the substring of s before y.
• z could be the part after y.

Now, if i "pump down" the string by taking i = 0, then the remaining string would be only xz which will definitely have unequal number of 0s and 1s which does not belong to the language L.

Thus we have reached a contradiction as we earlier assumed L to be regular.

Therefore, it is not regular.

If it was a little hard understanding the above part, consider an example. Let p be an integer 5. Let 0+1000+11101 be a string in L. (+ indicates concatenation) Let me take x to be "0", y be "1000", z be the remaining part 11101. Then if we perform x(y^i)z with i=0, the remaining string would be 011101 which is not a part of L. Thus irregular.

Note: the example was just a sample to make you understand the logic. One cannot decide the value of p randomly.