Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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).
In general if you want to prove that a language is CF, even if in this case the solution proposed by Steven is shorter and more elegant, you can see if there is a PDA that accepts it, even though it my be tough not only to find it but also to formally prove it accepts every string of the language.
