1,065 views
2 votes
2 votes
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

3 Answers

1 votes
1 votes

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.

reshown by
0 votes
0 votes

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 Tyes for {0, 1, 1100} and Tno for {0,1} 

0 votes
0 votes
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
edited by

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
140 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
141 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?