decidability

Question

S = { < M> | M is a DFA that accepts some string containing an equal number of 0s and 1s}. Then what will be S -

a) Recursive enumerable

b) undecidable

c) decidable

d) Turing co-recognizable

Comments

@Arjun Sir please help on this.

---

Is it not the case that if we are able to construct a DFA of a given language then this is a necessary and sufficient condition for that language to be decidable.

since DFA clearly separate the strings which belong to the language and which aren't.

I am not very much sure though.

---

We can construct a PDA which can accepts equal number of 0 and 1.

And then we can have a machine  DFA M.

Now we can intersect both and if there is a common string ,it means the DFA accepts at least one string of the given constraint.

If the intersection is empty ,then we will reject that DFA.

So,for Members we can say yes and for non members NO.

Hence it is recursive and decidable

Answer 1

We can solve this using Rice Theorem.
Tyes = {epsilon}   In epsilon number of a & b are equal.
Tno=   {0*1*}     Here number of a & b are not  always equal.

So Tyes & Tno exists. So undecidable as per Rice's 1st theorem.
Now Tyes is a proper subset of Tno so not Recursively Enumerable as per Rice's 2nd theorem.

http://gatecse.in/rices-theorem/

Now coming to options....

"Language L is called co-Turing-recognizable, if L' is Turing-recognizable. 
http://www.eecs.yorku.ca/course_archive/2006-07/F/2001/handouts/lect20.pdf

Now lets see if it's complement is RE,  If that is RE, then we can say here answer is D.
L'= unequal number of a & b.
Tyes= {abb}
Tno= {ab}
So undecidable.
But we cant find any such Tyes & Tno such that both are regular & Tyes is a proper subset of Tno.
From here we cant declare that it is RE. Here Rice theorem does not work.

But we are 90% sure from here (Option elimination+Rice thorem) that answer is D.
Not sure. Need some one to verify.

Comments

@Ahwan , not much satisfied with the above conclusion can you explain more

---

What is the source of this question ?
I need some one to verify the ans first.

---

the source is -

INTRODUCTION TO THE THEORY OF COMPUTATION ,MICHAEL SIPSER (3rd edition) problem no 4.17 (page no - 212)

Answer 2

it will be undecidable,

given a DFA, there is an algorithm to find language corresponding to given DFA, now upto this point every thing is decidable, now

problem is,

"given a regular language, whether there exist some string in this language containing an equal number of 0s and 1s ?"

according to rice's theorem it will be undecidable, since there is T_yes for {0, 1, 1100} and T_no for {0,1} 

Comments

Your Tyes is not proper subset of Tno.I think this is the required property.Non monotone is not satisfied

Answer 3

I am not sure,
M is a DFA that means they are talking about specific DFA ,ie there exists a regular expression for all strings accepted by the dfa ..
Thus we can give all the strings belonging to the regular expression and check.

But here they are talking about  dfa that accepts some string (1 string).thus its decidable..
correct me if i am wrong

Comments

Yes, I also think it is decidable