in Theory of Computation retagged by
900 views
2 votes
2 votes

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

  1. $L_1L_2$
  2. $L_1\cap L_2$
  3. $L_1\cap R$
  4. $L_1\cup L_2$
in Theory of Computation retagged by
by
900 views

1 comment

B is correct since  CFLs are not closed under intersection
0
0

4 Answers

2 votes
2 votes
Correct answer is B.

Option A:

L1.L2 = Concatenation of two context free languages, which is also a context free languages.

Option C:

Any Context free language is closed under regular intersection, Hence this is also a context free langauge.

Option D:

Context free languages are closed under Union.

Hence the only option left is B as Context free languages are not closed under Intersection.
by
0 votes
0 votes
CFL are not closed under intersection .

For eg  : Let L1 be {a^n b^n c^k | n,k is integer greater than 0 }

              Let L2 be {a^k b^n c^n | n,k is integer greater than 0 }

 

Now intersection of them will be {a^n b^n c^n } which is not context free . Hence answer is B
0 votes
0 votes
THe answer is B.As we know from the property of closed Cfg is not closed on intersection
0 votes
0 votes
Option B) L1 intersection L2 is correct answer, as If l1 and l2 are two CFG’s their intersection need not be context free.

eg- L1={a^n b^n c^m| n>0 and m>=0} and L2={a^m b^n c^n|n>=0 and m>=0} , Therefore ,

L1 intersection L2 = {a^n b^n c^n| n>=0} need not be context free.
Answer:

Related questions