GATE 2022 CS – Question 23
Which of the following statements is/are TRUE?
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
Check each statement.
- **(A) False.** Not every subset of an RE language is recursive. Take $\Sigma^*$ (which is recursive, hence RE); it has subsets that are not even RE, such as an undecidable language.
- **(B) True.** If both $L$ and $\bar L$ are RE, run a recogniser for each in parallel. Exactly one halts and accepts, so $L$ is decidable, i.e. recursive.
- **(C) True.** Every CFL is decidable (e.g. by CYK), so its complement is also decidable, hence recursive.
- **(D) True.** Regular languages are closed under intersection, and every regular language is a deterministic CFL.
Answer: B, C, D.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2022 CS Q47
- GATE 2022 CS Q48
- GATE 2021 CS (CS1) Q11
- GATE 2020 CS Q18
- GATE 2020 CS Q20
- GATE 2020 CS Q42
All Regular and Context-Free Languages, Pumping Lemma questions →