GATE CS 2022 Q38 — Context-free Grammars and Push-down Automata

Let us analyze the properties of the given languages:

• $L_1 = \{ ww \mid w \in \{a,b\}^* \}$: This is a classic non-context-free language. However, its complement $\overline{L_1}$ is context-free.
• $L_2 = \{ a^n b^n c^m \mid m,n \ge 0 \}$: This is a deterministic context-free language (DCFL) because we can match $a$'s and $b$'s using a deterministic pushdown automaton (DPDA) and then read any number of $c$'s.
• $L_3 = \{ a^m b^n c^n \mid m,n \ge 0 \}$: This is also a DCFL because we can skip $a$'s and then match $b$'s and $c$'s using a DPDA.
• $L_2 \cap L_3 = \{ a^n b^n c^n \mid n \ge 0 \}$: This is a well-known non-context-free language.

Now, let us evaluate each statement to find which ones are FALSE:

1. Statement A (TRUE): $L_1$ is indeed not context-free, and both $L_2$ and $L_3$ are deterministic context-free.
2. Statement B (FALSE): $L_2$ is context-free, so the claim that "neither $L_1$ nor $L_2$ is context-free" is false.
3. Statement C (FALSE): $L_2 \cap L_3$ is not context-free, so the claim that all three are context-free is false.
4. Statement D (FALSE): The complement of $L_1$ is context-free, so the claim that "neither $L_1$ nor its complement is context-free" is false.

Thus, the false statements are B, C, and D.