1 vote

Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free?

- $L_1 \cap \overline{L_2} \\$
- $\overline{\overline{L_1} \cup \overline{L_2}} \\$
- $L_1 \cup (L_2 \cup \overline{L_2}) \\$
- $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$

5 votes

The options should be $b,c,d$.

Options –

(a) The Complement of CFL is Recursive. The intersection of Recursive and Regular is Recursive.

(b) It is $L_1 \cap L_2$ and intersection of CFL and regular is CFL.

(c)It is $\sum$ itself as $L_2 \cup \bar{L_2}$ is $\sum$ and union of $\sum$ and $L_1$ is $\sum$ which is regular and thus CFL.

(d) Solving this you will get $L_2$ which is CFL. See the image below.

We can write the $(d)$ option as,

$= (23 \cap 34) \cup (14 \cap 34)$

$= (3) \cup (4)$

$= L_2$

1 vote

Given : $L_1$= Regular language

$L_2$=CFL

A) $L_1\cap \bar L_2$: as we know that CFL is not closed under complement operation. CFL complement is REC.

therefore Reg $\cap$ $\overline{CFL}$ =REC which is not CFL.

hence option A is wrong here.

B) $\overline{(\bar L_1\cup \bar L_2)}$: this can be written as $\overline{\overline{L_1}}\cap\overline{\overline{L_2}}\implies L_1\cap L_2$.

hence Regular $\cap$ CFL is CFL because CFL is closed with regular intersection.

option $B$ is correct.

C) $L_1\cup(L_2\cup \bar L_2)$: CFL complement is REC language.

CFL$\cup$ REC is REC language and union with regular language is REC which is not CFL.

so option $C$ is false here.

D) $(L_1\cap L_2)\cup(\bar L_1\cap L_2)$; This can be written as:

(regular $\cap$ CFL)$\cup$( Regular $\cap$ CFL)

$\implies$ (regular $\cap$ CFL)= CFL, (Regular $\cap$ CFL)=CFL

$\implies$ CFl$\cup $CFL=CFL

Option $D$ is correct.

$\therefore$ Option $B$ and $D$ is correct.

0 votes

**B,C,D**

Some insights beforehand:

**Not Closed **under **Intersection**:

$L_1=\{a^nb^*c^n\},L_2=\{a^nb^nc^*\}$ , $L_1\cap L_2=\{a^nb^nc^n\}$ not a CFL

**Closed **under **Union: **

Let both of these CFLs be represented using grammars with start symbols $S_1$ and $S_2$, we define a new symbol $S^{’}$ such that $S^{’}\to S_1/S_2$ note, we definitely have a NPDA but could be represented under DPDA if the language allows it to be(2 RLs).

**Not Closed** under **Complementation:**

$L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}$

We know that **intersection **isn’t closed under context free languages and **union **is closed under CFL(NPDA) so it must be the case that **complementation isn’t** closed under CFL.

Example: $L=\{a^nb^nc^n\}$ not a CFL but, $\overline{L}$ is and infact can be solved using a NPDA.

**Intersection and Union** of a **CFL **is **RL **is **CFL**.

Now,

- $L_2$ is complemented so, needn’t be a CFL.

- $\overline{\overline{L_1}\cap\overline{L_2}}=L_1\cup L_2$ union of a CFL and RL is a CFL
- $L_1\cup(L_2\cup\overline{L_2})=L_1\cup(\Sigma^*)=\Sigma^*$ hence a CFL.
- $(L_1\cap L_2)\cup(\overline{L_1}\cap L_2)=L_2$ or it’s a union of two CFLs if you don’t bother to solve.