TOC DECIDABILITY

Question

Let E={<M>| M is a DFA that accepts some strings with more 1's than 0's}

Show that E is decidable.

How can E be decidable. How can a DFA compare between number of 1's and 0's.

From the question I know that it's not talking about all, but some. The things is even some should not be decidable. isn't it?

Comments

Yes they are not talking about all possible strings. They are talking about 'some' strings for which number of 1s is greater than no. of 0s.

So if the input set for dfa is finite then we can say that it is decidable. (( it may be a logic behind this question.

---

Let say there are finite number of strings.(we don't know the strings, and yes machine also doesn't know too .. it's understandable)

Say the machine E has accepted some strings and rejected some strings.

Then how can we say what strings are accepted and rejected by the machine. Whether the strings accepted contains at least one string having number of 1's greater than 0's is still not known...

Answer 1

This can be done by using closure properties of CFLs.

Let the language

$$A = \{ \text{w} |  \text{w has more 0s than 1s\}}$$ be the CFL.

We can construct a TM $S$ for the given language in the following way:

1. We construct $B$ such that $B = A \, \cap L(M)$ (note that B will be a CFL)
2. Then, we can use testing emptiness of CFG on this, which we know is decidable.
3. If $S$ is empty, we reject. Else, we accept.

Comments

Shouldn't it be L(M)=A INTERSECTION B.

because we don't know L(M), we know A and B

---

We do know M - M is a regular language which has a DFA. The exact details of the language doesn't really matter.