Ace Test Series: Theory Of Computation - Recursive And Recursively Enumerable Languages

Question

Comments

can you please explain in detail please @saurabh

---

see as u r right on L1 intersection L2 is  {M accepts strings which is equal to 2016 strings}
means it does not accept string everything else
nd both L nd L'r not re

---

What is given answer???

Answer 1

$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?

Comments

@ Arjun sir, is complement of non-RE always non-RE??? Isn't it an open problem???

---

Complement of r.e. may or may not be r.e. (Because r.e. languages are not closed under complement). But for the given non r.e. language, its complement is also not r.e.

---

Thank you.