patternMinor
Does this argument prove CFLs are not closed under union?
Viewed 0 times
thiscflsargumentareunionclosedproveunderdoesnot
Problem
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
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!
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?
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!
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?
Solution
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}}$.
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}}$.
Context
StackExchange Computer Science Q#116464, answer score: 6
Revisions (0)
No revisions yet.