Mathematical Foundation of Computer Science

DHARM

320 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l Assume a new start symbol S.

l The set P of productions contains all the productions of P 1 , all the productions of P 2

and a new production S → S 1 S 2 that are responsible to generate the strings of G 1

concatenated with strings of G 2 so,

S → S 1 S 2 ∪ P 1 ∪ P 2

Since P 1 and P 2 are the productions of G 1 and G 2 , that are CFG, hence grammar G is

CFG.

So, we conclude that L 1. L 2 is CFL.

Further assume that if string x ∈ L 1 and y ∈ L 2 then

S 1 ⇒N x and S 2 ⇒N y

Thus, for the concatenation of these strings xy (Fig. 11.28 shows the derivation tree)
following is the derivation sequence,

S ⇒ S 1 S 2 ⇒N x S 2 ⇒N xy, that is L 1. L 2

Hence L 1. L 2 ∈ L(G).

S 1 S 2

S

xy

Fig. 11.28

Context free language is closed under kleeny closure operation
Kleeny closure of context free language is context free language. To prove this property we
assume that L is a CFL and its grammar G = (VN, VT, S, P). Now construct a new grammar G′
using the definition of G (without violating the properties of CFG) so that it generates kleeny
closure of L, that is L.
Before constructing the grammar G′ we recall following facts for L,
l A new string ∈ be the part of its language so G′ has a null production. Because we
can’t alter the rules of set P so we introduce a new production for this cause, deriving
from a new non terminal S’ that is the start symbol for G′.
S′ → ∈
l Since L* = ∈ ∪ L. L ∪ L. L. L ∪ .......
From S we can generate the possible string of (single) L. For the generation of strings
of multiple L’s, G′ must have following production
S′ → S S′
Like as, S′ ⇒ SS′ ⇒ S. ∈ ⇒ S (that generates the strings ∈ L)
S′ ⇒ SS′ ⇒ SSS′ ⇒ SS. ∈ ⇒ SS (that generates the strings ∈ L. L)

and S′ ⇒N SS......S (that generates the strings ∈ L. L. L......L)