The Gateway to Computer Science Excellence
+25 votes

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
in Theory of Computation by Boss (30.8k points)
edited by | 2.3k views
is recursive enemurable language is close under union
In options there is no 2nd statement 😂

1 Answer

+32 votes
Best answer

Answer is D.

$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 by
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.

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


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,142 users