in Theory of Computation edited by
4,811 views
22 votes
22 votes

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$

in Theory of Computation edited by
4.8k views

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
1
1
@Ankit Kabi Inverse Homomorphism is closed under regular language.
0
0
@ankit sir your anwer is awesome thank you sir
0
0

6 Answers

2 votes
2 votes
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.

selected by
24 votes
24 votes

Correct Option: B

CFL's are not closed under intersection.

edited by

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.
0
0
Can any one give proof for why option c is true..
0
0
@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
2
2
1 vote
1 vote
Ans: B not closed under intersection and complementation and hence set difference too.
edited by

2 Comments

hence difference ?? Did nt get it ..
0
0

Puja Mishra

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.

4
4
1 vote
1 vote

option b is right

edited by

3 Comments

Please give example for option B.
0
0
thanks bro
0
0
Answer:

Related questions