2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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 }

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So B-A is equal to B-A1 or B-A2 or B-A3 or B-A4 ? $\endgroup$ – Mary Star Jan 13 '14 at 23:08
  • 2
    $\begingroup$ @MaryStar: No -- set minus does not distribute over union. $\endgroup$ – Chris Dodd Jan 13 '14 at 23:10
  • $\begingroup$ Ok... Do I have to use B-A=B∩A' ? $\endgroup$ – Mary Star Jan 13 '14 at 23:17
  • 1
    $\begingroup$ @MaryStar -- yes, that is the normal definition of set minus $\endgroup$ – Chris Dodd Jan 13 '14 at 23:18
  • $\begingroup$ @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. $\endgroup$ – G. Bach Feb 3 '14 at 16:32
3
$\begingroup$

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!

| cite | improve this answer | |
$\endgroup$

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.