GATE CSE 2021 Set 1 | Question: 1

Question

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?

• A. $L_1 \cap L_2$
• B. $L_1 \cdot L_2$
• C. $L_1- L_2$
• D. $L_1\cup L_2$

Answer 1

Correct Option: $C$

---

Given,                                       

• $L_1-$ Regular Language (RL)         
• $L_2-$ Context-Free Language (CFL)

$(A)$ $L_1 \cap L_2 \to$  CFL

Because intersection operation with regular languages is closed under CFLs.

Hence, True.

$(B)$ $L_1.L_2\to$   CFL

Every regular language is a CFL and  CFLs are closed under concatenation.

Hence, True.

$(C)$ $L_1-L_2$ $\equiv$ $L_1 \cap L_2 ^{c}$.

Suppose, let’s consider $L_1 = \Sigma^*$ and $L_2$ as any CFL and we get $L_1 \cap \overline{L_2} = \overline{L_2}.$

Since CFLs aren’t closed under complementation, this means $L_1 – L_2$ NEED NOT be a CFL!

Hence, False.

$(D)$ $L_1\cup L_2 \to$ CFL 

Since CFLs are closed under union operation and a regular language is also a CFL.

Hence, True.

Ref: Closure Property of Language Families

Comments

https://gatecse.in/closure-property-of-language-families/ in this it is given Regular ⊂ DCFL ⊂CFL ⊂ REC ⊂ RE.

regular language is subset of CFL,

if we take L1= Σ* and L2 some CFL then it won’t be subset right?

i am not understanding this “Suppose, let’s consider L1=Σ∗ and L2 as any CFL and we get L1∩L2 “

 

 

 

---

$L1-L2 = Reg \ – \  CFL = Reg\cap CFL' = Reg \ \cap CSL = CSL$

But, $L2 – L1 = CFL \ –  \ Reg = CFL\cap Reg' = CFL\cap Reg = CFL$ 

(Because intersection operation with regular languages is closed under ALL LANGUAGES.)

Answer 2

C option is correct.

Cfl are not closed under -

Comments

Correct, for example $\bar{ww}$ is CFL but $\Sigma^* – \bar{ww}$ is CSL.

Answer 3

• A) CFL intersection with Regular language is CFL 
• B) All Regular languages are CFL, CFLs are closed under concatenation
• D) CFLs are closed under union
• C) CFLs are not closed under set difference

Option C) is correct