The GATE Grind

GATE 2015 CS – Question 28

Theory of Computation · Turing Machines and Undecidability · 1 mark · Multiple choice

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?

I. $\overline{L_1}$ (complement of $L_1$) is recursive

II. $\overline{L_2}$ (complement of $L_2$) is recursive

III. $\overline{L_1}$ is context-free

IV. $\overline{L_1} \cup L_2$ is recursively enumerable

  1. I only
  2. III only
  3. III and IV only
  4. I and IV only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) I and IV only

Explanation

Every context-free language is recursive, and recursive languages are closed under complement, so $\overline{L_1}$ is recursive (I). The complement of a language that is recursively enumerable but not recursive is not recursive (II is false). Context-free languages are not closed under complement, so III need not hold. A recursive language is recursively enumerable, and recursively enumerable languages are closed under union, so $\overline{L_1} \cup L_2$ is recursively enumerable (IV).