edited by
6,202 views
23 votes
23 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$

edited by

6 Answers

Best answer
7 votes
7 votes

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

option b is right

edited by
1 votes
1 votes
Ans: B not closed under intersection and complementation and hence set difference too.
edited by
Answer:

Related questions

30 votes
30 votes
6 answers
1
Kathleen asked Oct 9, 2014
10,077 views
Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string).$(00)^ * (\varepsilon +0)$$(00)^*$$0^*$$0(00)^*$(i) and (ii)(ii) a...
19 votes
19 votes
4 answers
4
Kathleen asked Oct 9, 2014
9,040 views
What is the equivalent Boolean expression in product-of-sums form for the Karnaugh map given in Fig $B\overline{D} + \overline{B}D$$(B + \overline{C} +D) (\overline{B} + ...