Register

GATE CSE 1996 | Question: 2.8

• edited by
6,341 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
User Avatar

6 Answers

1 votes
1 votes

 

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.

Hence CFL are not closed under intersection and complementation and also difference .

 

User Avatar
0 votes
0 votes

(B) is Right Option.

CFL’S are not closed under complement and intersection. In this way we can easily eliminate Option A & D as these are unions and concatenation.

Let’s come to option C

L1∩R → During intersection of different languages (here Regular and CFL), take Upper bound of the intersecting languages, which is CFL, So this is CFL.

Let’s come to option B

both languages are CFL and we know CFLS ‘re not closed under intersection so (B) is the correct option   

 

 

 

 

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

30 votes
30 votes
6 answers
5
Kathleen asked Oct 9, 2014
10,228 views
GATE CSE 1996 | Question: 1.8
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) and (iii) (i) and (iii) (iii) and (iv)
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...
User Avatar
19 votes
19 votes
4 answers
8
Kathleen asked Oct 9, 2014
9,129 views
GATE CSE 1996 | Question: 2.24
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} + C + \overline{D})$ $(B + {D})(\overline{B} +\overline{ D})$ $(B + \overline{D})(\overline{B} + {D})$
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} + ...
User Avatar
Link Copied!