in Theory of Computation edited by
3,219 views
4 votes
4 votes

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free?

  1. $L_1 \cap L_2$
  2. $L_1 \cdot L_2$
  3. $L_1- L_2$
  4. $L_1\cup L_2$
in Theory of Computation edited by
by
2439 3623 5536
3.2k views

Subscribe to GO Classes for GATE CSE 2022

3 Answers

5 votes
5 votes
 
Best answer

Correct Option: $C$


Given,                                       

  • $L_1-$ Regular Language (RL)         
  • $L_2-$ Context-Free Language (CFL)

$(A)$ $L_1 \cap L_2 \to$  CFL

Because intersection operation with regular languages is closed under CFLs.

Hence, True.

$(B)$ $L_1.L_2\to$   CFL

Every regular language is a CFL and  CFLs are closed under concatenation.

Hence, True.

$(C)$ $L_1-L_2$ $\equiv$ $L_1 \cap L_2 ^{c}$.

Suppose, let’s consider $L_1 = \Sigma^*$ and $L_2$ as any CFL and we get $L_1 \cap \overline{L_2} = \overline{L_2}.$

Since CFLs aren’t closed under complementation, this means $L_1 – L_2$ NEED NOT be a CFL!

Hence, False.

$(D)$ $L_1\cup L_2 \to$ CFL 

Since CFLs are closed under union operation and a regular language is also a CFL.

Hence, True.

Ref: Closure Property of Language Families

edited by
by
53 150 261

1 comment

https://gatecse.in/closure-property-of-language-families/ in this it is given Regular ⊂ DCFL ⊂CFL ⊂ REC ⊂ RE.

regular language is subset of CFL,

if we take L1= Σ* and L2 some CFL then it won’t be subset right?

i am not understanding this “Suppose, let’s consider L1=Σ∗ and L2 as any CFL and we get L1∩L2 “

 

 

 

0
0
1 vote
1 vote
C option is correct.

Cfl are not closed under -
by
2 3 7

1 comment

Correct, for example $\bar{ww}$ is CFL but $\Sigma^* – \bar{ww}$ is CSL.
0
0
0 votes
0 votes
  • A) CFL intersection with Regular language is CFL 
  • B) All Regular languages are CFL, CFLs are closed under concatenation
  • D) CFLs are closed under union
  • C) CFLs are not closed under set difference

Option C) is correct 

by
37 89 187
Answer:

Related questions