Showing the following language is decidable

Question

Let $BAL_{DFA} = \{<M> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \}$ Show that $BAL_{DFA}$ is decidable.

Generally such questions seem to be solved by constructing a DFA that accepts all strings that have equal number of 0's and 1's and then constructing a DFA that accepts the intersection of the one we constructed and M. Then we can run $E_{DFA}$ to check. Here we can't construct a DFA that accepts $0^n1^n$ as it is not regular, but we could construct a PDA. I think Sipser's book gives a way. But intersection of two PDA's need not necessarily be a PDA. Also we don;t have anything like $E_{PDA}$ which is decidable. I am not aware. How could we solve this. I know this is a solved excercise in Sipser, but I want to understand how one could approach such questions.

Answer 1

You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.

So. We have some DFA $M$, and we can build a PDA $N$ which recognizes the language $\{w : \#_0(w) = \#_1(w)\}$, where $\#_a(w)$ denotes the number of occurrences of the symbol $a$ in the string $w$ (note this is not the same as $\{0^n 1^n : n \geq 0\}$). Then $L(M) \cap L(N)$ is context-free. Checking if $M$ accepts a balanced string amounts to checking if $L(M) \cap L(N)$ is the empty language. But it's known that emptiness of context-free languages is decidable. Given $M$, we can easily construct the machine which recognizes $L(M) \cap L(N)$ and check if $L(M) \cap L(N)$ is empty. So your problem is decidable!