The GATE Grind

GATE 2017 CS – Question 48

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 2 marks · Multiple choice

Consider the following languages over the alphabet $\Sigma = \{a, b, c\}$. Let $L_1 = \{a^n b^n c^m \mid m, n \geq 0\}$ and $L_2 = \{a^m b^n c^n \mid m, n \geq 0\}$.

Which of the following are context-free languages?

I. $L_1 \cup L_2$

II. $L_1 \cap L_2$

  1. I only
  2. II only
  3. I and II
  4. Neither I nor II

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) I only

Explanation

Each of $L_1$ and $L_2$ is context-free, and context-free languages are closed under union, so $L_1 \cup L_2$ is context-free. Their intersection is $\{a^n b^n c^n \mid n \geq 0\}$, which is not context-free. So only I holds.