UGC NET CSE | December 2018 | Part 2 | Question: 36

Question

Consider $R$ to be any regular language and $L_1$, $L_2$ be any two context-free languages. Which of the following is correct?

• A. $\overline{L_1}$ is context free
• B. $\overline{(L_1 \cup L_2)} – R$ is context free
• C. $L_1 \cap L_2$ is context free
• D. $L_1 – R$ is context free

Comments

I think only option 2( in fact it is Regular)

Answer 1

$1.\; \bar{L_1}$  is context free.

$\bullet$ CFLs are not closed under complementation.(DCFL are closed)

So first one is not correct.

$2.\; L_1- R$   is context free.

it can also be written as $L1\cap\bar{R}$  

$\bullet$ regular languages are closed under complementation.

$\bullet$ CFL are closed under intersection with regular language.

So $L_1-R$ is context free.

$3.\;\overline{(L_1UL_2)}-R\;$   is context free.

$\implies (\bar{L_1}\cap\bar{L_2})-R$  

$\bullet$ CFLs are not closed under complementation and moreover not closed under intersection.

So statement 3 is not correct.

only (2) is correct.

Answer 2

Basic Points :-

1. CFL is not closed under Intersection
2. CFL is not closed under complementation
3. CFL is closed under union
4. CFL is closed under Intersection with Regular Language
5. Regular Language is closed under complementation

 $\overline{L_1}$ where L$_1$ is CFL ===> as per point 2, it is not always correct.

$\overline{L_1 \cup L_2}$ where L$_1$ and L$_2$ are CFL ==> L$_1 \cup L_2$ is CFL ==> $\overline{L_1 \cup L_2}$ is not CFL always.

$L_1 \cap L_2$ is not always CFL as per point 1.

$L_1 - R = L_1 \cap \overline{R}  = L_1 \cap R $ ===> always true as per point 4

ref : https://gatecse.in/closure-property-of-language-families/