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$

2 Answers 2

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 }

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

$\endgroup$
0

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.