# 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^{n}b^{n} | n >= 0 } and L2 = { c^{m}d^{m} | m >= 0 }

**1. CFL are closed under Union**

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

**2. CFL are closed under Concatenation**

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

**3. CFL are closed under Kleen Closure**

L1* = { a^{n}b^{n} | 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^{n}b^{n}c^{m} | n >= 0 and m >= 0 } and L2 = (a^{m}b^{n}c^{n} | n >= 0 and m >= 0 } are CFL’s.

Now apply intersection on given CFL’s.

L3 = L1 ∩ L2 = { a^{n}b^{n}c^{n} | 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