Closure Properties of CFG

Context Free languages (CFG) are accepted by pushdown automata (PDA) but not by finite automata (FA). Context free grammar generates the Context free languages. Let discuss some Closure Properties of CFG.
 
CFG Closure Properties

Consider L1 and If L2 are two context free languages where   L1 = { aⁿbⁿ | n >= 0 } and L2 = { c^md^m | m >= 0 }

1. CFL are closed under Union

As L3 = L1 ∪ L2 = { aⁿbⁿ ∪ c^md^m | n >= 0, m >= 0 } is also context free.

2. CFL are closed under Concatenation

As L3 = L1.L2 = { aⁿbⁿc^md^m | n >= 0, m >= 0 } is also context free.

3. CFL are closed under Kleen Closure

L1* = { aⁿbⁿ | n >= 0 }* is also context free.

4. CFL are not closed under Complementation

Complementation of context free language L1 which is ∑* – L1 is not a CFL.

5. CFL are not closed under Intersection

Suppose L1 = { aⁿbⁿc^m | n >= 0 and m >= 0 } and L2 = (a^mbⁿcⁿ | n >= 0 and m >= 0 } are CFL’s.

Now apply intersection on given CFL’s.
L3 = L1 ∩ L2 = { aⁿbⁿcⁿ | n >= 0 } is not a context free language because there are two comparisons in derived language after intersection.

Note:  Deterministic Context Free Language (DCFL)  are closed only under complementation and Inverse Homomorphism