4,798 views

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?

1. $L_1.L_2$

2. $L_1 \cap L_2$

3. $L_1 \cap R$

4. $L_1 \cup L_2$

3 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

6 Answers

Best answer

Answer is Option B

Option A

CFL’s are closed under CONCATENATION operation & hence $L_1.L_2$ is necessarily a context free language.

Option B

CFL’s are NOT closed under INTERSECTION operation & hence $L_1 \cap L_2$ is NOT NECESSARILY a context free language.

Option C

CFL’s are closed under INTERSECTION operation with Regular language & hence $L_1 \cap R$ is necessarily a context free language.

Option D

CFL’s are closed under UNION operation & hence $L_1 \cup L_2$ is necessarily a context free language.

Correct Option: B

CFL's are not closed under intersection.

4 Comments

Hey! Do you know facts!
If A is a superset of B then if a language is B then it is automatically A. Thus if a language is regular then it is automatically CFL, CSL, REL.
Can any one give proof for why option c is true..
@chirudeepnamini

consider   $a^{n}b^{^{n}}$ $\cap$ a*b*.=$a^{n}b^{^{n}}$ which is CFL…

Note- If L1 and L2  are from different class of languages then L1 $\cup$ L2 and L1 $\bigcap$ L2 will be of higher class and may/may not be of lower class
Ans: B not closed under intersection and complementation and hence set difference too.

2 Comments

hence difference ?? Did nt get it ..

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.

thats y CFL are not closed under intersection and complementation and hence difference.

option b is right

3 Comments

Please give example for option B.
thanks bro
Answer:

27 votes
5 answers
1
7,940 views
40 votes
3 answers
2
26 votes
2 answers
3
17 votes
4 answers
4
6,579 views