# Counterexample that B-A can be NOT context free

Given that A is a context free language and B is a regular language, B-A can be not context free as it is equal to B ∩ A', and context free languages are not closed under complement. Could you give me a counterexample?

Consider the languages

• B = { a*b*c* } -- an obviously regular language.
• A1 = { aibjc* | i > j }
• A2 = { aibjc* | i < j }
• A3 = { a*bicj | i > j }
• A4 = { a*bicj | i < j }
• A = A1 ∪ A2 ∪ A3 ∪ A4

The An langauges are all context-free, so their union is also context free, but the language B-A is the non-context free language { aibici }

• So B-A is equal to B-A1 or B-A2 or B-A3 or B-A4 ? – Mary Star Jan 13 '14 at 23:08
• @MaryStar: No -- set minus does not distribute over union. – Chris Dodd Jan 13 '14 at 23:10
• Ok... Do I have to use B-A=B∩A' ? – Mary Star Jan 13 '14 at 23:17
• @MaryStar -- yes, that is the normal definition of set minus – Chris Dodd Jan 13 '14 at 23:18
• @ChrisDodd "set minus does not distribute over union" - it's true that in general $A \setminus (B \cup C) = (A \setminus B) \cup (A \setminus C)$ does not hold, but $(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ always holds. – G. Bach Feb 3 '14 at 16:32

Just because the CFLs aren't closed under complement doesn't mean that the complement of a CFL is never a CFL.

As a hint: Σ* and ∅ are regular and therefore context-free.

Hope this helps!