# GATE CSE 2021 Set 2 | Question: 12

1 vote
401 views

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

1. $L_1 \cap \overline{L_2} \\$
2. $\overline{\overline{L_1} \cup \overline{L_2}} \\$
3. $L_1 \cup (L_2 \cup \overline{L_2}) \\$
4. $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$

edited
0

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$

edited
0
in option D both are CFL ( regular intersection with CFL)   union of two CFL is CFL
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
@Hira C is given as CFL in official key but I totally agree with you reasoning. @Arjun Sir can you please shed some light here?

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,

1. $L_2$ is complemented so, needn’t be a CFL.
1. $\overline{\overline{L_1}\cap\overline{L_2}}=L_1\cup L_2$ union of a CFL and RL is a CFL
2. $L_1\cup(L_2\cup\overline{L_2})=L_1\cup(\Sigma^*)=\Sigma^*$  hence a CFL.
3. $(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.

edited

## Related questions

1
394 views
For a string $w$, we define $w^R$ to be the reverse of $w$. For example, if $w=01101$ then $w^R=10110$. Which of the following languages is/are context-free? $\{ wxw^Rx^R \mid w,x \in \{0,1\} ^* \}$ $\{ ww^Rxx^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxw^R \mid w,x \in \{0,1\} ^* \}$ $\{ wxx^Rw^R \mid w,x \in \{0,1\} ^* \}$
​​​​​​​Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$
Consider the following sets, where $n \geq 2$: $S_1$: Set of all $n \times n$ matrices with entries from the set $\{ a, b, c\}$ $S_2$: Set of all functions from the set $\{0,1,2, \dots, n^2-1\}$ to the set $\{0, 1, 2\}$ Which of the following ... to $S_2$ There exists a surjection from $S_1$ to $S_2$ There exists a bijection from $S_1$ to $S_2$ There does not exist an injection from $S_1$ to $S_2$
In the context of compilers, which of the following is/are $\text{NOT}$ an intermediate representation of the source program? Three address code Abstract Syntax Tree $\text{(AST)}$ Control Flow Graph $\text{(CFG)}$ Symbol table