GATE 2021 CS – Question 11

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

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?

$L_1 \cap L_2$
$L_1 \cdot L_2$
$L_1 - L_2$
$L_1 \cup L_2$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $L_1 - L_2$

Explanation

$L_1 - L_2 = L_1 \cap \overline{L_2}$, and CFLs are not closed under complement. The other three are always CFLs.