The GATE Grind

GATE 2023 CS – Question 24

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

Which of the following statements is/are CORRECT?

  1. The intersection of two regular languages is regular.
  2. The intersection of two context-free languages is context-free.
  3. The intersection of two recursive languages is recursive.
  4. The intersection of two recursively enumerable languages is recursively enumerable.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) The intersection of two regular languages is regular.; (C) The intersection of two recursive languages is recursive.; (D) The intersection of two recursively enumerable languages is recursively enumerable.

Explanation

Regular, recursive and RE languages are all closed under intersection. CFLs are not closed under intersection, e.g. {a^n b^n c^m} ∩ {a^m b^n c^n}.