Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $F$ be a finite language, and $L$ an arbitrary language. Show that if $L$ is context-free, then so is $L-F$.

How would one prove this? Is it possible?

share|improve this question
This answer to an earlier, more general question outlines a proof using automata. –  Brian M. Scott May 30 '12 at 4:46
@BrianM.Scott Intuitively what's on that post makes sense but I don't know how to build a solution to this question out of it. –  Jack Kobil May 30 '12 at 4:56
Are you familiar with pushdown and finite state automata as recognizers of context-free and regular languages? –  Brian M. Scott May 30 '12 at 4:58
@BrianM.Scott yes, to some extent. –  Jack Kobil May 30 '12 at 5:02
@BrianM.Scott such as a language is able to be generated by a context-free grammar if a pushdown automaton can be made to accept it. Is that what you're referring too? And all regular languages have a corresponding context free grammar. –  Jack Kobil May 30 '12 at 5:04
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.