Question 48

1. $L_1 = \{ww \mid w \in \{a, b\}^*\}$ is a well-known non-context-free language (provable via the pumping lemma for CFLs).
2. $L_2 = \{a^n b^n c^m \mid m, n \ge 0\}$ is a Deterministic Context-Free Language (DCFL), accepted by a DPDA that matches $a$'s and $b$'s on its stack and then scans $c$'s.
3. $L_3 = \{a^m b^n c^n \mid m, n \ge 0\}$ is also a DCFL.
4. $L_2 \cap L_3 = \{a^n b^n c^n \mid n \ge 0\}$, which is well-known to be non-context-free.
5. The complement of $L_1$, $\overline{L_1} = \{x \in \{a, b\}^* \mid x \ne ww\}$, is a context-free language (it can be generated by a non-deterministic PDA that guesses the mismatch position).

Now evaluate each statement to find which are FALSE:

• (A) TRUE: $L_1$ is not context-free, and $L_2, L_3$ are DCFLs.
• (B) FALSE: $L_2$ is context-free.
• (C) FALSE: $L_2 \cap L_3$ is not context-free.
• (D) FALSE: The complement $\overline{L_1}$ is context-free.

Thus, statements (B), (C), and (D) are FALSE.