[Math] DCFL are closed under Intersection with Regular Languages

automatacontext-free-grammardiscrete mathematicsformal-languagesregular-language

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}$.

Best Answer

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.

Related Question