Question 32

Let us examine the two languages:

• $L_1 = \{0^p 1^q 0^r \mid p, q, r \ge 0\}$. This is simply the language denoted by the regular expression $0^* 1^* 0^*$. Thus, $L_1$ is regular.
• $L_2 = \{0^p 1^q 0^r \mid p, q, r \ge 0, p \ne r\}$. This requires comparing $p$ and $r$ ($p < r$ or $p > r$). A non-deterministic pushdown automaton can push zeros, ignore ones, and verify whether the number of trailing zeros differs from the leading zeros. Thus, $L_2$ is a deterministic context-free language (DCFL), hence context-free.

Now evaluate each statement:

• (A) $L_2$ is context-free: TRUE, as shown above.
• (B) $L_1 \cap L_2$ is context-free: Since $L_2 \subseteq L_1$, $L_1 \cap L_2 = L_2$, which is context-free. Even generally, the intersection of a regular language ($L_1$) and a CFL ($L_2$) is always a CFL. Thus, TRUE.
• (C) Complement of $L_2$ is recursive: Every CFL is recursive (decidable). The class of recursive languages is closed under complementation. Therefore, the complement of $L_2$ is recursive. Thus, TRUE.
• (D) Complement of $L_1$ is context-free but not regular: Since $L_1$ is regular, and regular languages are closed under complementation, the complement of $L_1$ is regular! Saying it is "not regular" is false.

Hence, statement (D) is FALSE.