GATE CSE 2017 | Set 2 | Question: 04

Question

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

• A. I, II and IV only
• B. I and III only
• C. II and IV only
• D. I only

Comments

for iii) option)
L-R
check normally L.Rcomplement
now check cfl.cfl which is closed under concat
so its context free

---

why we are not considering DCFL ?

---

@Ritiksri8  L - R = 
not concatination operaton, it's intersectin operation. 

@Js___  we're not considering DCFL because in questoin they're asking about CFL and regular, and DCFL is also there but need not to be show. 

Answer 1

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.

Comments

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.

---

Nice example for the third statement.

Answer 2

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.

Answer 3

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

Answer 4

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

Comments

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.

---

https://gateoverflow.in/3571/gate2006-it-32 

Answer 5

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

Answer 6

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

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