GATE CS 2021 Set 1 Q1 — Context-free Grammars and Push-down Automata

To determine which language is not necessarily context-free, let us analyze the closure properties of Context-Free Languages (CFLs) and Regular languages:

• Option A ($L_1 \cap L_2$): The intersection of a regular language and a context-free language is always context-free. This is a standard closure property of CFLs.
• Option B ($L_1 \cdot L_2$): Since every regular language is also a context-free language, and CFLs are closed under concatenation, $L_1 \cdot L_2$ is always context-free.
• Option D ($L_1 \cup L_2$): Since every regular language is context-free, and CFLs are closed under union, $L_1 \cup L_2$ is always context-free.
• Option C ($L_1 - L_2$): This is not necessarily context-free. We can show this using a counterexample:

Counterexample:

Let the alphabet be $\Sigma = \{a, b, c\}$.

• Let $L_1 = a^*b^*c^*$, which is a regular language.
• Let $L_2 = \{a^i b^j c^k \mid i \neq j \text{ or } j \neq k\}$, which is a context-free language.

Now, let us find $L_1 - L_2$:

The resulting language $\{a^n b^n c^n \mid n \ge 0\}$ is a well-known non-context-free language. Thus, $L_1 - L_2$ is not necessarily context-free.