is {w in {0,1}* | #0(w) = #1(w)} a regular language?

Question

is L = {w in {0,1}* | #0(w) = #1(w)} a regular language?

I've managed to prove it is context free, but this doesn't really help.

I've also saw a hint (here - prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?) to look at the complementing language which is {w in {0,1}* | #0(w) != #1(w)}, but I didn't manage to prove it is not regular either (I guess if I have then it would mean L is not regular.

Please help (I would prefer an explanation than a hint, I think i'm missing something basic here)

Thanks

Answer 1

No, this language isn't regular. @MJD has a great intuitive explanation for this in the comments: determining whether a string is in this language requires tracking the relative numbers of 0s and 1s, and there are infinitely many possible relative values to track.

There are many ways to prove this one. You could, as @MJD suggests, use the pumping lemma. But I prefer the following approach. You know that the intersection of two regular languages is always regular. What's the intersection of this language with the language $\mathtt{0}^\star\mathtt{1}^\star$? Is that resulting language regular? What does that tell you?

Answer 2

This is too long for a comment, but I wanted to add some intuition as to why this language is not regular.

One characterization of regular languages is that $\textsf{REG} = \textsf{DSPACE}(O(1)) = \textsf{NSPACE}(O(1))$.

In other words, regular languages are precisely those that are decided by Turing Machines with a read-only input-tape where we can't go backwards, and a work tape that allows us exactly $b$ bits, for some $b$ you get to choose when designing the TM. This means that $b$ is fixed for every string we consider.

The Pumping Lemma for Regular Languages (in its contrapositive form) effectively tells us that if we can find some string in the language that requires more than $b$ bits on the tape, then the language is not regular. So intuitively, if we allow our Turing Machine only $b$ bits of space to work, then we can only track $2^{b}$ consecutive $0$'s. So now pick a string with more than $2^{b}$ consecutive $0$'s.

Again, the Pumping Lemma for Regular Languages formalizes the intuition I just described.