NIELIT 2016 DEC Scientist B (CS) - Section B: 3

Question

If $L1$ is CFL and $L2$ is regular language which of the following is false?

• A. $L1-L2$ is not Context free
• B. $L1$ intersection $L2$ is Context free
• C. $\sim L1$ is Context free
• D. Both (A) and (C)

Comments

c option is correct because CFL is not closed under complement

---

L1 = {a^nb^n,n>=0},

L2 =E^*(consider as sigma power *)

then complement of L2 is {} i.e phi(set of empty language)
 

A. L1−L2=L1⋂L2′

    Which is CFL. So A is false as it can be CFL.

B. Intersection of CFL and RL is CFL always. So B is correct.

C. CFL isn't closed under complement. So C is false.

So D is correct.

Answer 1

L1 = {$a^nb^n, n >=0$}, L2 =$ (a+b)^*$, L2' = { }

 

A. $L1 - L2 = L1 ⋂ L2'$

$L1 ⋂ L2' = ${ }

Which is CFL. So A is false as it can can be CFL.

B. Intersection of CFL and RL is CFL always. So B is correct.

C. CFL isn't closed under complement. So C is false.

So D is correct.

Answer 2

Property of CFL 

1. Not closed under intersection 
2. Not closed under complement
3. If intersected with Regular it is closed.

Now A – B is equal to  A ∩ B’ 

and complement of regular is regular 

Looking at all these cases answer is D 

Answer 3

Option c) is correct as CFL’s are not closed under complementation.