Search code examples
regexalgorithmregular-languageautomataproof

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

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?

Solution

  • 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.