3
$\begingroup$

Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language.

I'm just not sure how to use their properties to formally show this. Thanks for all the help in advance.

$\endgroup$
  • $\begingroup$ If A is context-free, there is a push down automaton that accepts A. Try to modify this automaton such that it accepts A-B. $\endgroup$ – A.Schulz Jul 20 '12 at 18:08
  • $\begingroup$ What have you tried? Do you want a full solution or only hints (the only reason I ask is that the way you phrase the question, one might reasonably assume the latter, as did @YuvalFilmus below). $\endgroup$ – Patrick87 Jul 20 '12 at 19:44
6
$\begingroup$

Hint: If $A$ is context-free and $R$ is regular then $A \cap R$ is context-free.

$\endgroup$
  • $\begingroup$ Hint+1: if $R$ is regular, so is $\bar{R}$. $\endgroup$ – Luke Mathieson Jul 21 '12 at 2:47

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.