Consider the following languages. $$L_1 = \{0^p 1^q 0^r \mid p,q,r \ge 0\}$$ $$L_2 = \{0^p 1^q 0^r \mid p,q,r \ge 0, p e r\}$$ Which one of the following statements is FALSE?

Let us analyze each statement:

1. Nature of $L_1$: $L_1 = \{0^p 1^q 0^r \mid p, q, r \ge 0\} = 0^* 1^* 0^*$, which is a regular language.

2. Complement of $L_1$: Since regular languages are closed under complementation, the complement of $L_1$ is also regular (and hence context-free). Statement (D) claims that the complement of $L_1$ is context-free *but not regular*, which is FALSE.

3. Nature of $L_2$: $L_2 = \{0^p 1^q 0^r \mid p

e r\}$can be parsed using a deterministic pushdown automaton (by matching the number of leading$0$'s with trailing$0$'s and ensuring they are not equal). Thus,$L_2$ is a deterministic context-free language (DCFL), so (A) is true.

4. Intersection $L_1 \cap L_2$: Since $L_2 \subseteq L_1$, $L_1 \cap L_2 = L_2$, which is context-free, making (B) true.

5. Complement of $L_2$: DCFLs are closed under complement, so the complement of $L_2$ is a DCFL, and all context-free languages are recursive (decidable), making (C) true.

Therefore, the statement that is FALSE is (D).