# DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

1. $L_1 \cap L_2$ is a deterministic CFL
2. $L_3 \cap L_1$ is recursive
3. $L_1 \cup L_2$ is context free
4. $L_1 \cap L_2 \cap L_3$ is recursively enumerable

My attempt :

1. False, Since $\text{DCFLs are not closed under union nor intersection}$.
2. False, that should be recursive enumerable but not recursive.
3. True.
4. True.

Can you explain for option $(1)$, is DCFL are closed under Intersection with Regular Languages?

Somewhere, it explained as $\text{DCFL are closed under Intersection with Regular Languages}$.

Consider the automata that decide $L_1$ and $L_2$, $DFA_1 = (Q_1,\Sigma,\delta_1,q_{s1}, F_1)$ and $DPDA_1 = (Q,\Sigma,\Gamma, \delta_2,q_{s2},Z,F_2)$. We assume that they are defined over the same alphabet.

We can construct the intersection of the two automata as follows.

Let $DPDA_{L1\cup L2} = (Q_3,\Sigma,\Gamma, \delta_3,q_{s3},Z,F_3)$. Where

• $Q_3 = Q_1\times Q_2$
• $\Sigma = \Sigma$
• $\Gamma = \Gamma$
• $\delta_3: Q_3\times\Sigma\times\Gamma \to Q_3\times\Gamma^*$

$\delta_3((q_1,q_2),a,b) = (\delta_1(q_1,a),\delta_2(q_2,a,b))$

• $q_{s3} = (q_{s1},q_{s2})$
• $Z=Z$
• $F_3 = F_1 \times F_2$

This is a PDA that recognises $L_1\cap L_2$, and therefore $L_1\cap L_2$ is DCFG.

• Thanks for explanation. – 1 0 Dec 13 '15 at 6:17