GATE CS 2006 Q33 — Regular and Context-free Languages

To find the false statement, let us analyze each option based on the closure properties of language families:

• Option A: $L_1 \cap L_2$ is a deterministic CFL.
  Deterministic Context-Free Languages (DCFLs) are closed under intersection with regular languages. Since $L_2$ is a DCFL and $L_1$ is regular, $L_1 \cap L_2$ is guaranteed to be a DCFL. This statement is true.
• Option B: $L_3 \cap L_1$ is recursive.
  Let us choose $L_1 = \Sigma^*$ (which is a regular language). Then, $L_3 \cap L_1 = L_3 \cap \Sigma^* = L_3$. Since $L_3$ is given to be recursively enumerable but not recursive, the intersection $L_3 \cap L_1$ is not recursive. Thus, this statement is false.
• Option C: $L_1 \cup L_2$ is context free.
  Since every DCFL is also a CFL, $L_2$ is a CFL. Regular languages ($L_1$) are also CFLs. Since Context-Free Languages are closed under union, $L_1 \cup L_2$ is a CFL. This statement is true.
• Option D: $L_1 \cap L_2 \cap L_3$ is recursively enumerable.
  The intersection of a regular language and a DCFL, $L_1 \cap L_2$, is a DCFL, which is also a Recursively Enumerable (RE) language. Since RE languages are closed under intersection, the intersection of $(L_1 \cap L_2)$ with the RE language $L_3$ is also RE. This statement is true.

Therefore, the false statement is B.