# Proving that a language is a CFL

Assume that $$L_1 \subseteq \Sigma^*$$ is a CFL and that $$y \in \Sigma^∗$$ is a string.

I need to prove that the language $$L_2 = \{x \in L_1 \mid x \text{ does not contain y as substring}\}$$ is a CFL.

I tried pumping lemma for CFLs, but it seems that is for disproving that languages are CFLs. I also tried to create a CFG for this language, but I'm having a hard time. I even took a look at the membership problem for CFGs.

Any ideas on how I would go about proving this?

• Think closure. Apr 27 at 7:55

The language $$L' = \Sigma^* y\Sigma^*$$ is regular and, by the closure properties of regular languages, so is $$\Sigma^* \setminus L'$$. Then, by the closure properties of context-free languages, $$L_2 = L_1 \cap (\Sigma^* \setminus L')$$ is context-free (since it can be written as the intersection of a context free language with a regular language).