UGC NET CSE | Junet 2015 | Part 3 | Question: 62

Question

Given the following two statements:

$S_1$: If $L_1$ and $L_2$ are recursively enumerable languages over $\Sigma^*$, then $L_1 \cup L_2$ and $L_1 \cap L_2$ are also recursively enumerable.

$S_2$: The set of recursively enumerable languages is countable.

Which of the following is true?

• A. $S_1$ is correct and $S_2$ is not correct
• B. $S_1$ is not correct and $S_2$ is correct
• C. Both $S_1$ and $S_2$ are not correct
• D. Both $S_1$ and $S_2$ are correct

Comments

Detailed Video Solution: https://www.youtube.com/watch?v=fl8Z3oM2EJk&t=8706s 

S2: Set of ALL recursively enumerable languages is countable. Proof HERE 

---

Countability Complete Course, with Proofs, Variations & All type of questions covered: https://youtube.com/playlist?list=PLIPZ2_p3RNHgXosiQv-gL1PvJkcHokW1p&feature=shared 

---

I have a doubt here.

Let L1, L2 be RE languages.
L1 U L2 = L1’ ⋂ L2’

We know that RE languages are not closed under complement. Hence, L1’ and L2’ may not be R.E. Then how we can say that L1’ ⋂ L2’ must be RE ??

Answer 1

Both are True.

RES are closed under intersection and union.

Set of RES is similar to set of Turing machines which we can count so RES also.

 

https://books.google.fr/books?id=hsxDiWvVdBcC&pg=PA281&lpg=PA281&dq=is+the+set+of+recursively+enumerable+languages+is+countable&source=bl&ots=rdGwViXpgR&sig=46GGkz-DM5-zIluIIH3F-R7ilFk&hl=en&sa=X&ved=0CCcQ6AEwAWoVChMIjMidg9vcxgIVBJQeCh2GhQvO#v=onepage&q=is%20the%20set%20of%20recursively%20enumerable%20languages%20is%20countable&f=false

Answer 2

L1 and L2 are R.E. then L1 ∪ L2 is RE and L1 ∩ L2 is also RE since RE is closed under union and intersection. The set of recursively enumerable languages is countable infinite. So Both are true. D is ans