Search code examples
setcontext-free-grammardiscrete-mathematicsformal-languagescontext-free-language

Is the the set difference of 2 context free languages context free?

I've searched on the internet and most say just say that context free languages are closed for union, concatenation, reversal, and Kleene Star. Are they also closed for set difference?

Solution

  • The context-free languages are not closed under set difference. One way to see this is to note that

    1. the context-free languages are not closed under complementation,
    2. the language Σ* is context-free, and
    3. for any language L, the complement of L is given by Σ* - L.

    Therefore, if the CFLs were closed under set difference, then they'd be closed under complementation... except that they aren't. :-)