292 views
0 votes
0 votes

1 Answer

1 votes
1 votes

Answer B)

TM that accepts atleast 1 string-It is a non trivial property of TM. But not satisfies non monotonic property.

Rice Theorem(1st case)- Any non trivial  property of TM is undecidable.

It satisfies here. Because in trivial property we are talking about a certain case, where 'yes' and 'no' answer is obvious. But when we talk about atleast or atmost, those are uncertain case. So, satisfies non-trivial property.

Rice Theorem(2nd case)- Any non monotonic property of TM is unrecognizable

If we think 'yes' cases of TM is $\Phi$ and 'no' cases of TM is $\Sigma ^*$, then non monotonic property only satisfies, when $TMyes\subset TMno$.

But here we cannot say it satisfied, as $\Phi$ is not satisfied here.

So, it is not TM decidable

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

edited by

Related questions

0 votes
0 votes
0 answers
1
Hemanth_13 asked Dec 25, 2018
357 views
$L= {WW^RX| W,X=(a+b)^+}$ My question was why can’t this be regular??Consider below regular expression $aa(a+b)^+ + ab(a+b)^+ +ba(a+b)^+ + bb(a+b)^+$==>$(aa+ab+ba+bb)(...
0 votes
0 votes
0 answers
3
Mk Utkarsh asked Sep 15, 2018
551 views
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
3 votes
3 votes
2 answers
4