9,154 views

Let $L_1, L_2$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT?

1. $L_1 \cup L_2$ is context-free
2. $\overline{L_1}$ is context-free
3. $L_1 - R$ is context-free
4. $L_1 \cap L_2$ is context-free
1. I, II and IV only
2. I and III only
3. II and IV only
4. I only

ERROR IN GO PDF THIRD OPTION – SIGN MISSING.

### Subscribe to GO Classes for GATE CSE 2022

Statement I is TRUE as CFGs are closed under union.

Statement II is FALSE as CFGs are not enclosed under complementation.

Statement III is TRUE as $L1−R$ can be written as $L1\cap \overline{R}$. Regular language are closed under complementation and intersection of CFG and Regular is CFG.

Statement IV is FALSE as CFGs are not enclosed under intersection.

So, I and III are correct. Option B.

by
6 9 18

But, I read somewhere that CFL are not closed under Set Difference. We can say that R is also an CFL coz RL is a subset of CFL and since, CFL is not closed under Set Difference, we cannot say that L1−R is CFL.

$1:cfl-reg=Cfl\ \cap\ reg'=clf$

$2:reg-cfl=reg\ \cap\ cfl'=$may or may not be cfl.

@kushagra

lets take case 1.

regular =   take everything

cfl  -   {a^n b^n / n>=0}

regular intersection  CFL =  CFL  but not regular.....

case 2.

lets take

regular =   take nothing (phi)

cfl -  {a^n b^n / n>=0}

regular intersection cfl  =   phi..........which is regular ...and Every regular language is context-free

Hence  III statement is correct.

i think  it help.

intersection of two CFL are not closed operation, and CFL also not closed under complimentation,
CFL-reg we can write like this CFL $CFL\cap \bar{regular}$  so regular language closed under complimentation and intersection of CFL with regular is always CFL.
by
20 56 84
CFLs are closed under union operation and difference with a regular language.Hence option i and iii are correct.

But CFLs are not closed under intersection and complementation.so option ii and iv are wrong.

Ans:B) i and iii
by
26 72 121

okay CFL s are closed under Union

so  1 is correct

option 2: L1' is not CFL as it is not closed under complementation

option 3 is nothing but intersection with regular language which is CFL

3 is correct so

4 is not correct as cfl is not closed under intersection

so from this i get 1,2,3 correct but that is not in option i think your option 2 will be a different..

so 1 and 3 correct

by
39 118 232

In Third statement CFL-Reg=>CFL(Intersect)Reg

here Reg. is closed under Intersection but CFL is not closed

And Every Reg is CFL so We can write CFL(Intersect)CFL which May Not be CFL BY its closure Property.

1) CFLs are closed under union.

2)CFLs are not enclosed under complementation and intersection.

3) L1−R = L1 intersection R' = L1 intersection R So CFL on intersection with Regular it will be CFL

So Option B

by
2 7 16

Only I and III are correct , so option B is correct.

1. CFG are not closed under complement. and  IV. CFG are not closed under intersection.
by
2