3,219 views

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?

1. $L_1 \cap L_2$
2. $L_1 \cdot L_2$
3. $L_1- L_2$
4. $L_1\cup L_2$

### Subscribe to GO Classes for GATE CSE 2022

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.

by
53 150 261

### 1 comment

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 “

C option is correct.

Cfl are not closed under -
by
2 3 7

### 1 comment

Correct, for example $\bar{ww}$ is CFL but $\Sigma^* – \bar{ww}$ is CSL.
• 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

by
37 89 187