retagged by
908 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$
retagged by

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

1 votes
1 votes
2 answers
1
admin asked Mar 31, 2020
1,673 views
If there is in NP-Complete language L whose complement is in NP, then complement of any language in NP is inPNPboth (A) and (B)None of these
2 votes
2 votes
2 answers
2
admin asked Mar 31, 2020
1,873 views
Which of the following regular expressions denotes a language comprising all possible strings over the alphabet $\{a,b\}$?$a^*b^*$$(a\mid b)^*$$(ab)^+$$(a\mid b^*)$
4 votes
4 votes
4 answers
4