2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Could you elaborate why intersection of context free language with regular language is context free. Thanks for pointing out the $0^n1^n$ mistake. $\endgroup$ – T.Harish Oct 7 at 2:12
  • $\begingroup$ 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)$. $\endgroup$ – Robert Andrews Oct 7 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.