The GATE Grind

GATE 2022 CS – Question 23

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple select

Which of the following statements is/are TRUE?

  1. Every subset of a recursively enumerable language is recursive.
  2. If a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ must be recursive.
  3. Complement of a context-free language must be recursive.
  4. If $L_1$ and $L_2$ are regular, then $L_1\cap L_2$ must be deterministic context-free.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) If a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ must be recursive.; (C) Complement of a context-free language must be recursive.; (D) If $L_1$ and $L_2$ are regular, then $L_1\cap L_2$ must be deterministic context-free.

Explanation

B holds because L and its complement both being RE implies L is recursive. C holds because CFLs are decidable, so their complements are recursive. D holds because regular languages are closed under intersection and every regular language is a DCFL. A is false, since subsets of Σ* include non-RE sets.