edited by
1,073 views
0 votes
0 votes

edited by

1 Answer

Best answer
3 votes
3 votes
$L$ is the set of TM descriptions each of which accepts exactly 2016 strings. So $L$ is a non-monotonic property of r.e. languages (add one more string to the set of strings being accepted and we get a NO case and $L(T_{yes)} \subset L(T_{no})$. Hence, $L$ is not even r.e.

$\bar L$ is also not even r.e., and we can apply monotonic property here also. Try for $T_{yes}$ and $T_{no}$ is obviously fixed as one which accepts exactly 2016 strings.

So, options A and D are false. Options B and C are true as one is $\phi$ and other is $\Sigma^*$ both of which are regular.

Why do you people solving ACE questions?
selected by

Related questions