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?

- $\bar{L}_{1}$ ( Compliment of $L_{1}$) is recursive
- $\bar{L}_{2}$ ( Compliment of $L_{2}$) is recursive
- $\bar{L}_{1}$ is context-free
- $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable

- I only
- III only
- III and IV only
- I and IV only

+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.

+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.

Therefore statement II. is false.

0

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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,391 comments

105,142 users