2.3k views

For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true?

1. $\bar{L}_{1}$ ( Compliment of $L_{1}$) is recursive
2. $\bar{L}_{2}$ ( Compliment of $L_{2}$) is recursive
3. $\bar{L}_{1}$ is context-free
4. $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable
1. I only
2. III only
3. III and IV only
4. I and IV only

edited | 2.3k views
0
is recursive enemurable language is close under union
+1
In options there is no 2nd statement 😂

$L_1$ is context-free and hence recursive also. Recursive set being closed under complement, $L_1$' will be recursive.

$L_1$' being recursive it is also recursively enumerable and Recursively Enumerable set is closed under Union. So, $L_1' \cup L_2$ is recursively enumerable.

Context free languages are not closed under complement, so $III$ is false

Recursive set is closed under complement. So, if $L_2$' is recursive, ($L_2$')'  $= L_2$ is also recursive which is not the case here. So, $II$ is also false.

by Veteran (431k points)
edited
+4
descrition for statement II. -> recursively enumerable is not closed under complementation. so given, L2 is recursively enumerable but not recursive, -> complement of L2 is not recursively enumerable hence not recursive also

Therefore statement II. is false.
0

@Arjun Why can't we use the same explanation for -

1. L1¯ ( Compliment of L1) is recursive

Explanation - L1 is context-free and hence recursive also. Recursive set being closed under complement, L1' will be recursive (as given by you)

I guess, it's because of the word Necessarily True and in 1) we take L1 = CFL and CFL are not closed under complement and hence L1 may or may not be CFL and L1 can only be REC iff L1' is CFL ,but that's not guaranteed.

whereas in 4) because of UNION and L2 being {R.E} it's a sure shot case of always being true?

Am I making any sense?