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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for explanation. $\endgroup$ – ً ً Dec 13 '15 at 6:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.