# Showing the following language is decidable

Let $$BAL_{DFA} = \{ \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.

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!
• Could you elaborate why intersection of context free language with regular language is context free. Thanks for pointing out the $0^n1^n$ mistake. Oct 7, 2019 at 2:12
• Take $N$ to be a non-deterministic PDA, and $M$ to be a DFA. Take the product machine $P$ of $N$ and $M$, where the accepting states correspond to the product of accepting states of $N$ and $M$. Have $P$ use its stack in exactly the same manner as $N$. It's not too hard to see that $P$ accepts a string $w$ if and only if both of $N$ and $M$ accept $w$, i.e., $L(P) = L(N) \cap L(M)$. Oct 7, 2019 at 3:10