retagged by
7,395 views
11 votes
11 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$
retagged by

3 Answers

Best answer
16 votes
16 votes

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
1 votes
1 votes
C option is correct.

Cfl are not closed under -
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 

Answer:

Related questions

16 votes
16 votes
1 answer
2
Arjun asked Feb 18, 2021
9,011 views
​​​​​​The ratio of boys to girls in a class is $7$ to $3$.Among the options below, an acceptable value for the total number of students in the class is:$21$$3...
11 votes
11 votes
1 answer
3