GATE CSE 2015 | Set 1 | Question: 3

Question

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}$ ( Complement of $L_{1}$) is recursive
2. $\bar{L}_{2}$ ( Complement of $L_{2}$) is recursive
3. $\bar{L}_{1}$ is context-free
4. $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable

• A. I only
• B. III only
• C. III and IV only
• D. I and IV only

Comments

is recursive enemurable language is close under union

---

In options there is no 2nd statement 😂

---

dm4006 yes, REL is closed under union.

Answer 1

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.

Comments

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?

---

I also have same doubt. L1'is actually CSL and therefore REC but some REC are not CSL. Therefore there are some REC which is not included in the L1'. Now, L1' ∪ L2 is actually ∪ of REC(actually CSL) and RE but not REC and how it will be equal to RE as it will still not include REC language completely.

I could interpret this using Chomsky hierarchy diagram.

Please confirm.

---

My doubt is that L1 could also be Recursive Enumerable. CFL not being closed under complement means that it could be any of its supersets.

Answer 2

The following statement is necessarily true:

L¯1 (Complement of L1) is recursive

The complement of a context-free language is recursive, because a context-free language can be recognized by a non-deterministic pushdown automata (PDA), and the complement of a language recognized by a PDA can be recognized by a deterministic finite automata (DFA), which is a simpler machine.

The following statement is not necessarily true:

L¯2 (Complement of L2) is recursive

The complement of a recursively enumerable but not recursive language may or may not be recursive. If L2 is recursive, then L¯2 is recursive. But if L2 is not recursive, then L¯2 is not recursive.

The following statement is not necessarily true:

L¯1 is context-free

The complement of a context-free language is not necessarily context-free. Since context-free languages can be recognized by pushdown automata, and the complement of context-free languages may not be recognizable by any pushdown automata, it may not be context-free.

The following statement is not necessarily true:

L¯1 ∪ L2 is recursively enumerable

The union of two languages may or may not be recursively enumerable. It depends on the specific languages L1 and L2, and whether or not their union is recursively enumerable can only be determined by analyzing the properties of those specific languages.