質問

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.

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top