DHARMNON-REGULAR GRAMMARS 321So, G′ includes following tuples,
l Set of non terminals i.e., VN ∪ S′,
l Set of terminals i.e., VT ∪ {ε},
l A new start symbol S′ and
l Set of productions i.e., P ∪ {S′ → S S′ | ε}
All the productions of G’ fulfilling the properties of CFG hence its language L* is a CFL.
Besides above discussed closure properties for context free languages nothing is predicted
for the operations like intersection and complementation.
Theorem 11.1. If L 1 and L 2 are CFLs then L 1 ∩ L 2 may or may not be a CFL.
Proof. The proof of the above theorem is seen by solving of following example.
Assume languages L 1 = {aI bI cJ/I ≥ 1, J ≥ 1} and L 2 = {aJ bI cI/I ≥ 1, J ≥ 1} and there are
generated from the grammars G 1 and G 2 respectively,
where G 1 is given as, S → AB
A → ab | aAb
B → c | cBand G 2 is given as, S → AB
A → a | aA
B → bc | bBc
These are context free grammars (CFGs) so L 1 and L 2 are CFLs.
However we find that, language L 1 ∩ L 2 contains all the strings of equal number of a’s,
b’s and c’s or
L 1 ∩ L 2 = {aI bI cI/I ≥ 1} = L (let)
For language L it is not possible to construct the context free language hence, L is not
CFL or L 1 ∩ L 2 is not a CFL.
Theorem 11.2. If L 1 is a CFL and L 2 is a regular language then L 1 ∩ L 2 is a CFL.
Proof. [Hint : Reader may prove this theorem with the help of Chamosky’s hierarchy]
Theorem 11.3. Let L be a CFL so its complement L may or may not be a CFL.
Proof. Theorem says that for the complement of the language L i.e.
L = Σ* – L
nothing is predicted such that for the remaining strings which are not in L not necessarily the
part of CFL. We can prove this by method of contradiction.
Assume that L 1 and L 2 are CFLs then
L 1 ∪ L 2 = (L 1 ∩L ) 2 [DeMorgan Law]= (L 12 ∪L )
Since union of CFLs is CFL so the intersection is CFL that is a contradiction. Hence,
complement of language L is not a CFL.