Closure Properties Of Context Free Grammar

Context free grammer (CFG) generates the Context free languages (CFL) which are accepted by pushdown automata (PDA) but not by finite automata (FA). Let’s discuss some of the closure properties of Context free grammer.
 
Closure Properties of CFG

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 is closed under Union

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

2. CFL is closed under Concatenation

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

3. CFL is closed under Kleen Closure

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

4. CFL is not closed under Complementation

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

5. CFL is 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 CFLs.
L3 = L1 ∩ L2 = { aⁿbⁿcⁿ | n >= 0 } is not context-free because there are two comparisons in derived language after intersection.

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