DHARMNON-REGULAR GRAMMARS 319
11.13 Properties of Context Free Languages...........................................................................
In the previous chapter of regular expressions we have seen that certain operations are de-
fined over regular expressions so that its base case definitions are unaltered these are called
closure properties of regular expressions. Like that some operations are also defined over
context free languages that are guaranteed to return context free language. We shall now
study these operations as closure properties of context free languages.
Among these properties:
l Context free languages are closed under ∪ operation
l Context free languages are closed under concatenation operation
l Context free language is closed under kleeny closure operationContext free languages are closed under ∪ operation
This property of context free language states that union operation between CFLs return the
CFL. To prove this closure property assume that L 1 and L 2 are context free languages that are
generated from CFG G 1 and G 2 respectively, where
G 1 = (VN1, VT1, S 1 , P 1 ) and G 2 = (VN2, VT2, S 2 , P 2 )
Now construct a new grammar G(to take in mind that it generates L 1 ∪ L 2 ) that has
following tuples,
l The set of non terminals VN = VN1 ∪ VN2 ∪ {S} where S is a new start symbol
(Assume VN1 ∩ VN2 = ∅)
l The set of terminals VT = VT1 ∪ VT2
l A new start symbol S
l The set P of productions are S → S 1 | S 2 ∪ P 1 ∪ P 2 where, S 1 and S 2 are reachable
from S and so P 1 and P 2 which are defined for G 1 and G 2 respectively.
Since G 1 and G 2 are CFG so G = (VN, VT, S, P) is a CFG.
The constructed CFG G generates the language L 1 ∪ L 2. Hence, language is a CFL.
Further, we see that,
If x ∈ L 1 then it generates from grammar G as,
S ⇒ S 1 ⇒N x(all G 1 productions are in G)
If y ∈ L 2 then from grammar G it is generated with following derivation,S ⇒ S 2 ⇒N y(all G 2 productions are in G)
Thus, L 1 ∪ L 2 ∈ L(G).Context free languages are closed under concatenation operation
The second closure property says concatenations of context free languages are context free
language. Assume L 1 and L 2 are CFLs that are generated from CFGs G 1 and G 2 respectively,
where, G 1 = (VN1, VT1, S 1 , P 1 ) and G 2 = (VN2, VT2, S 2 , P 2 )
Now we construct the grammar G that will generate L 1. L 2 certainly has following tuples,
l The set of non terminals VN contains all the non terminals of G 1 as well as of G 2 with
a new start symbol S i.e.,
VN = VN1 ∪ VN2 ∪ S
l The set of terminals contains all the terminals of G 1 as well as of G 2 i.e.,
VT = VT1 ∪ VT2