Suppose that $L_{1}$ is a regular language and $L_{2}$ is a context-free language.Which one of the following languages is NOT necessarily context-free?

Open in App

Solution

$L_{1} \to R e g$
$L_{2} \to C o n t e x t - f r e e$
(a) $L_{1} . L_{2} = R e g . C F L = C F L C F L = C F L$
(b) $L_{1} \cup L_{2} = R e g \cup C F L = C F L$
(c) $L_{1} - L_{2} = L_{1} \cap_{2}$
$= R e g \cap ¯ ¯¯¯¯¯¯¯¯¯¯ ¯ C F L = R e g \cap ¯ ¯¯¯¯¯¯¯¯¯ ¯ C S L$
$= R e g \cap C S L = C S L$
(d) $L_{1} \cap L_{2} = R e g \cap C F L = C F L$
So (c) is not necessarily CFL.

Suggest Corrections

Similar questions

L_{1}

L_{2}

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

L_{1}

L_{2}

L_{1} a n d L_{2}

L_{1} : R e g u l a r, L_{2} : C o n t e x t - f r e e, L_{3} : R e c u r s i v e, L_{4} : R e c u r s i v e l y e n u m e r a b l e .

_{3} \cup L_{4}

_{2} \cup L_{3}

_{1} \cap L_{2}

L_{1} \cup_{2}

Join BYJU'S Learning Program