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

Question

Comments

I think B.

since L intersection L' = phi and phi is REL

L union L' = sigma* and it is not REL

---

@Digvijaysingh

Firstly...(sigma)* is regular so it's REL also.

Secondly...L is not a language...it is an encoding for Turing machine.

---

Yes it is non recursively enumerable language..So L' is not guaranteed to be REL.

But union of any language L and its complement will lead to Kleene's Closure ..So C) is correct and intersection of L and L' is also phi as they are complement of each other and hence disjoint..

Hence B) is also correct.

---

A and D can directly be eliminated.

But for option B.L and its intersection with its complement with given phi. So, I now considered this problem as : L = {<M> | L(M) accepts $\phi$} and this is not REL.

Similarly for C, it becomes if L(M) = $\sum ^*$ and it is semi-decidable.

---

can u explain how the intersection of the languages results in phi

---

^it is nt phi

---

L1 is non-RE L2 is RE. What is non-RE intersect RE?????

---

a is correct ans

---

L2 is RE and L1 non-RE  

L1 intersection L2 is  {M accepts strings which is equal to 2016 strings}  which is I guess RE

---

^no it is not re u can use rice 2nd thm

---

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.