GATE CSE 1996 | Question: 2.8

Question

If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one?

• A. $L_1.L_2$

• B. $L_1 \cap L_2$

• C. $L_1 \cap R$

• D. $L_1 \cup L_2$

Comments

CFLs are not close for CIDSQ.

C- Compliment

I- Intersection

D- Difference (due to Intersection)

S- Subset

Q- Quotient

Subset and Inverse Homomorphism are not closed for any type of language

---

@Ankit Kabi Inverse Homomorphism is closed under regular language.

---

@ankit sir your anwer is awesome thank you sir

Answer 1

 

let P and Q are CFL 

we know that CFL are not closed under intersection and complement.

so difference of P and Q also not closed as P-Q = P ∩ Q' , hence not closed.

Hence CFL are not closed under intersection and complementation and also difference .

 

Answer 2

(B) is Right Option.

CFL’S are not closed under complement and intersection. In this way we can easily eliminate Option A & D as these are unions and concatenation.

Let’s come to option C

L1∩R → During intersection of different languages (here Regular and CFL), take Upper bound of the intersecting languages, which is CFL, So this is CFL.

Let’s come to option B

both languages are CFL and we know CFLS ‘re not closed under intersection so (B) is the correct option   

 

 

 

 

Comments

100.  Note: Every regular language is context-free language.