Let $L_{1}$ be a regular language and $L_{2}$ be a context-free language. Which of the following languages is/are context-free?

Open in App

Solution

$L_{1} \to R e g u l a r$
$L_{2} \to C F L$
1. $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$
= CSL (need not be CFL)
2. $¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯_{1} \cup_{2} = L_{1} \cap L_{2} = R e g \cap C F L = C F L$
3. $L_{1} \cup (L_{2} \cup_{2}) = L_{1} \cup \sum^{} = \sum^{}$
=Regular and hence CFL
4. $(L_{1} \cap L_{2}) \cup (_{1} \cap L_{2}) = (L_{1} \cup_{1}) \cap L_{2}$
= $\sum^{*} \cap L_{2}$
= $L_{2} = C F L$

Suggest Corrections

Similar questions

L_{1} L_{2}

L_{1} \cup L_{2}

_{1}

L_{1} - R

L_{1} \cap L_{2}

L_{1}

L_{2}

L_{1}

L_{2}

\cap

L_{1} a n d L_{2}

Join BYJU'S Learning Program