Theory of Automata

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

1. CFL are closed under Union

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

2. CFL are closed under Concatenation

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



3. CFL are closed under Kleen Closure

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



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

 

Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan

cstaleem1@gmail.com

Website: CStaleem.com

Pin It on Pinterest