GATE CS 1999 Q2.4 — Regular and Context-free Languages

To determine which of the statements are false, let us analyze each option using the closure properties of Context-Free Languages (CFLs) and Regular languages.

We are given:

• $L_1$ is a Context-Free Language (CFL).
• $L_2$ is a Regular Language.

Analysis of Options:

• Option A: $L_1 - L_2$ is not context free

  We can rewrite the set difference as: $$L_1 - L_2 = L_1 \cap \sim L_2$$ Since $L_2$ is regular, its complement $\sim L_2$ is also regular (regular languages are closed under complementation).
  The intersection of a CFL ($L_1$) and a regular language ($\sim L_2$) is always a CFL. Therefore, $L_1 - L_2$ is guaranteed to be a context-free language.
  Thus, the statement "$L_1 - L_2$ is not context free" is FALSE.

• Option B: $L_1 \cap L_2$ is context free

  The intersection of a CFL ($L_1$) and a regular language ($L_2$) is always a CFL.
  Thus, this statement is TRUE.

• Option C: $\sim L_1$ is context free

  Context-free languages are not closed under complementation. For a general CFL $L_1$, its complement $\sim L_1$ may or may not be context-free.
  Thus, the statement "$\sim L_1$ is context free" is FALSE in general.

• Option D: $\sim L_2$ is regular

  Regular languages are closed under complementation. Since $L_2$ is regular, its complement $\sim L_2$ is also regular.
  Thus, this statement is TRUE.

Since the question asks for the statements that are false, the correct options are A and C.