GATE CS 2023 Q.24: Turing Machines and Chomsky Hierarchy

Which of the following statements is/are CORRECT?

The intersection of two regular languages is regular.

The intersection of two context-free languages is context-free.

The intersection of two recursive languages is recursive.

The intersection of two recursively enumerable languages is recursively enumerable.

Official answer and solution

Solution

Check closure properties under intersection for Chomsky hierarchy language classes.

Regular Languages: Closed under intersection (using product construction on DFAs). Thus, (A) is CORRECT.
Context-Free Languages: NOT closed under intersection (for example, $\{a^n b^n c^m\} \cap \{a^m b^n c^n\} = \{a^n b^n c^n\}$ , which is not context-free). Thus, (B) is INCORRECT.
Recursive (Decidable) Languages: Closed under intersection (simulate both deciders sequentially; accept if both accept). Thus, (C) is CORRECT.
Recursively Enumerable (Turing-Recognizable) Languages: Closed under intersection (interleave simulation of both Turing machines; accept if both halt and accept). Thus, (D) is CORRECT.

Final answer

Options (A, C, D)

Common trap

Assuming context-free languages are closed under intersection; they are closed under intersection with regular languages, but not with other CFLs.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.