Deterministic Context-Free Non-Closure Under Union

Counterexample idea: DCFLs are closed under complement. If they were also closed under union, then De Morgan's law would make them closed under intersection: L₁ ∩ L₂ = (L₁ᶜ ∪ L₂ᶜ)ᶜ. This contradicts the explicit intersection non-closure witness.

theorem DCF_notClosedUnderUnion : ¬ClosedUnderUnion is_DCF

Deterministic context-free languages over Fin 3 are not closed under union.

theorem DCF_notClosedUnderUnion_of_three {α : Type} [Fintype α] (a b c : α) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) : ¬ClosedUnderUnion is_DCF

Deterministic context-free languages are not closed under union for any finite alphabet containing three distinct symbols.

theorem DCF_notClosedUnderUnion_of_card {α : Type} [Fintype α] (hα : 3 ≤ Fintype.card α) : ¬ClosedUnderUnion is_DCF

Deterministic context-free languages are not closed under union for any finite alphabet with at least three symbols.