3
$\begingroup$

Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:

formula1

If CFLs were closed under complementation, then they must have also been closed under intersection, which is not the case. Now as we know, CFLs are not closed under intersection and complementation, can’t we use the following arguments to say CFLs are not closed under union, too!

formula2

In RHS, we are performing two operations viz. intersection and complementation, none of which guarantees the closure of the given CFLs. So, how does result of these two operations claims to remain a CFL? Doesn’t this prove that the result is not necessarily a CFL?

Yet, it’s known that CFLs are closed under union. Where is the flaw in the argument? Where am I wrong?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

Your first proof is valid. You are assuming by contradiction that CFLs are closed under complement and arriving at the absurd conclusion that they must be closed under intersection. Notice that this works for any intersection operation between two CFL languages.

Your second proof is wrong. You would need to assume that CFLs are closed under union and arrive at a contradiction. In your case your are not showing that, under the assumption, CFLs are closed under complement and intersection (hence the absurd). You are just showing that CFLs must be closed w.r.t. a particular operation in which you perform complements and intersections in some particular order.

Using the same logic I could prove the following erroneous claim.

Claim: CFLs are not closed under the identity operation $\textrm{Id}(L) = L$.

"Proof": CFLs are not closed under complement and, given a CFL $L$, $\textrm{Id}(L)$ can be written as $\textrm{Id}(L) = L = \overline{\overline{L}}$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for answering. But, I’m still confused. Suppose, CFLs are closed under union. But if they were closed under union, then they must have been closed under complementation and intersection operations(looking at the given equality equation). But that’s not true. What’s wrong in this line of reasoning? $\endgroup$
    – krisk
    Oct 29, 2019 at 20:45
  • $\begingroup$ "If they were closed under union, then they must have been closed under complementation and intersection" is false. You cannot just do any complementation and intersection and still obtain a CFL. It's only that particular sequence of operations that still yields a CFL language. This is the same as in my "fake proof" example: I cannot complement a CFL and be guaranteed to obtain a CFL (maybe it is, maybe it is not), but if I do the operation twice then the resulting language will necessarily be CF (or, if you want, CFLs are closed under double-complementation). $\endgroup$
    – Steven
    Oct 29, 2019 at 21:10
  • $\begingroup$ In other words, you just showed that CFLs are closed under complementation of the intersection of their complements (since CFLs are closed under finite union). A proof that CFLs are not closed under union would be: 1) assume CFLs are closed under union. 2) Show that $L_1 \cup L_2$ can be written using only unions and other operations that preserve membership in CF to simulate some other operation $L_1 \oplus L_2$. 3) Show that CFLs are not closed under $\oplus$, obtaining a contradiction. You are missing step 3, where $L_1 \oplus L_2 = \overline{\overline{L_1}\cap\overline{L_2}}$. $\endgroup$
    – Steven
    Oct 29, 2019 at 21:17
  • $\begingroup$ I totally understand now. Thanks. $\endgroup$
    – krisk
    Oct 29, 2019 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.