Closure Properties Of CFL

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 Language (CFL).
 
Closure Properties of CFL

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

Grammar (G1) for L1 is given below

Let G1 = (V,Σ,R,S), where:

• V={S1}

• Σ={a,b}

• R={S1→aS1b∣ϵ}

• S={S1}

L1 generates strings like: ε, ab, aabb, aaabbb, …………

Grammar (G2) for L2 is given below

Let G2 = (V,Σ,R,S), where:

• V={S2}

• Σ={c,d}

• R={S2→cS2d∣ϵ}

• S={S2}

L1 generates strings like: ε, cd, ccdd, cccddd, …………

Let’s prove the closure properties of Context-free Language (CFL).

1. CFL is closed under Union

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

• L1 generated strings = ε, ab, aabb, aaabbb, …………
• L2 generated Strings = ε, cd, ccdd, cccddd, …………

Since L3 is a union, it contains all strings from either L1 or L2. So,

L3 = L1 ∪ L2 = { ε, ab, aabb, aaabbb, …, cd, ccdd, cccddd, … }

Note:  abcd, aabbccdd, ……Those belong to a concatenation language, not a union.

Proof:  Let us prove a particular string i.e. “aabb” from L3 

• “aabb” ∈ L3 means it must be in either L1 or L2.

• Does “aabb” ∈ L1?

  • Yes, because:

    • It is of the form aⁿbⁿ, with n = 2

    • Two as followed by two bs

• So, “aabb” ∈ L1 ⊆ L3

Hence, it is proved that CFL is closed under union.

2. CFL is closed under Concatenation

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

• L1 generated strings = ε, ab, aabb, aaabbb, …………
• L2 generated Strings = ε, cd, ccdd, cccddd, …………
• L3 (as L1.L2) generated strings =  ε, abcd, aabbccdd, aaabbbcccddd, …………

Proof:  Let us prove the particular string i.e., “aabbccdd” from L3.

As aabb ∈ L1 for n = 2

ccdd ∈ L2 for m =2.

“aabbccdd” ∈ L1 ⋅ L2 = L3 for n,m =2.

Hence, it is proved that CFL is closed under concatenation.

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