2
$\begingroup$
  1. $L_1 \in \mathrm{CFL} \cap L_2\in \mathrm{CSL}$ is $\mathrm{CSL}$ because every $\mathrm{CFL}$ is $\mathrm{CSL}$ and by applying closure property of $\mathrm{CSL}$ under intersection, it's $\mathrm{CSL}$.

  2. $L_1 \in \mathrm{ RL} \cap L_2 \in \mathrm{CFL}$ is same as $\mathrm{CFL} \cap \mathrm{CFL}$ . As $\mathrm{CFL}$ is not closed under intersection, we promote $\mathrm{CFL}$ to $\mathrm{CSL}$. So $\mathrm{CSL} \cap\mathrm{CSL}$ is $\mathrm{CSL}$.

But, we know that 2nd is guaranteed to be $\mathrm{CFL}$ (also $\mathrm{CSL}$).

Why I am not able to arrive at the answer ($\mathrm{CFL}$) using closure properties for 2nd case ? Can't we apply closure properties when considering regular languages?

$\endgroup$
3
$\begingroup$

One of the closure properties of CFL is that they are closed onder intersection with regular languages. This can be directly applied, rather than first promoting the regular language to context-free language.

In general, if we want to know the family in which the intersection (or whatever operation $\oplus$) of two languages belongs, then we look for the smallest families $\mathrm{X}$ and $\mathrm{Y}$ that contain the two languages and for which we know an applicable closure property.

In your terminology, we "promote" as little as possible, but enough to find a family/families for which the closure property is known.

$\endgroup$
  • $\begingroup$ So do we promote if and only if it's not a regular language ? My doubt is when should we promote and find the class of the resulting language. $\endgroup$ – Rajesh R Dec 20 '17 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.