Tell me more ×
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.
up vote 0 down vote favorite

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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.