1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Think closure. $\endgroup$
    – greybeard
    Apr 27 at 7:55
1
$\begingroup$

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).

$\endgroup$
0
0
$\begingroup$

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.

$\endgroup$

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.