Introduction to Automata

# 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 = { anbn | n >= 0 } and L2 = { cmdm | m >= 0 }

### 1. CFL is closed under Union

As L3 = L1 ∪ L2 = { anbn ∪ cmdm | n >= 0, m >= 0 } is also context free.

### 2. CFL is closed under Concatenation

As L3 = L1.L2 = { anbncmdm | n >= 0, m >= 0 } is also context free.

### 3. CFL is closed under Kleen Closure

L1* = { anbn | 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 = { anbncm | n >= 0 and m >= 0 } and L2 = (ambncn | n >= 0 and m >= 0 } are CFL’s.

Now apply intersection on given CFLs.
L3 = L1 ∩ L2 = { anbncn | 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