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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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 }
-
$\begingroup$ So B-A is equal to B-A1 or B-A2 or B-A3 or B-A4 ? $\endgroup$ Commented Jan 13, 2014 at 23:08
-
2$\begingroup$ @MaryStar: No -- set minus does not distribute over union. $\endgroup$ Commented Jan 13, 2014 at 23:10
-
$\begingroup$ Ok... Do I have to use B-A=B∩A' ? $\endgroup$ Commented Jan 13, 2014 at 23:17
-
1$\begingroup$ @MaryStar -- yes, that is the normal definition of set minus $\endgroup$ Commented 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. BachCommented Feb 3, 2014 at 16:32
$\begingroup$
$\endgroup$
0
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!
answered Jan 13, 2014 at 22:52