in Theory of Computation retagged by
9,154 views
38 votes
38 votes

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
in Theory of Computation retagged by
by
111 187 266
9.2k views

2 Comments

Explain option iii please
1
1
ERROR IN GO PDF THIRD OPTION – SIGN MISSING.
0
0

Subscribe to GO Classes for GATE CSE 2022

6 Answers

34 votes
34 votes
 
Best answer

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.

edited by
by
6 9 18

3 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.

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

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

@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.

1
1
19 votes
19 votes
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
17 votes
17 votes
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
edited by
by
26 72 121
7 votes
7 votes

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

2 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.
2
2
0
0
1 vote
1 vote

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
0 votes
0 votes

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
Answer:

Related questions