COT6315 Formal Languages and Theory of Computation

Last modified 2/21/95.

Theorem 9.1: CFLs are closed under concatenation, union, Kleene closure

Proof

If L_1 and L_2 are in CFL, then there are CFGs G_1 = and G_2 = such that L_1 = L(G_1) and L_2 = L(G_2). Without loss of generality, let V1 ^ V2 = 0 and let T = T1 U T2. We now construct grammars for the desired languages. (The dot '.' will be used for concatenation for clarity.)

(L1.L2)

Let G = , where

• V = V1 U V2 U {S}
• P = P1 U P2 U {(S,{S1.S2})}

• x in L(G) <=> S =>* x AND x in T* <=>
• S => S1.S1 =>* x and x in T* <=>
• S => S1.S1 and x = x1.x2 and S1 =>* x1 and S2 =>* x2 and x in T* <=>
• x = x1.x2 AND x1 in L(G_1) AND x2 in L(G_2) <=>
• x in L_1.L_2

(L1 U L2)

Let G = , where

• V = V1 U V2 U {S}
• P = P1 U P2 U {(S,{S1, S2})}

• x in L(G) <=> S =>* x AND x in T* <=>
• S => S1 and S1 =>* x OR S => S2 and S2 =>* x and x in T* <=>
• x in L(G_1) OR x in L(G_2) <=>
• x in L_1 or x in L_2 <=> x in L_1 U L_2.

(L1*)

Let G = , where

• V = V1 U {S}
• P = P1 U {(S,{S1.S, e})}

• x in L(G) <=> S =>* x AND x in T* <=>
• S => e = x OR S =>* S1.S1...S1 =>* x AND x in T*
• S => e = x OR S =>* x AND x = x1.x2...xk AND Si =>* xi and xi in T*
• x in L(G_1)^k for some k >= 0 <=>
• x in L_1*