SOLUTION:

Context-free languages are closed under union, concatenation, and Kleene star.

Suppose G1 = (V1,1,R1, S1) and G2 = (V2,2,R2, S2).

S1 → aS1b

S1 →ǫ

For G2 we have

S2 → cS2d

S2 →ǫ

Then L (G1) = anbn:n≥0anbn:n≥0. Also, L (G2) = cndn:n≥0cndn:n≥0

1) Union

G = (V1 ∪ V2 ∪ {S},∪_1 ∪_2, R, S) where R = R1 ∪ R2 ∪ {S → S1, S → S2} and S is a new

symbol.

Then L (G) = L (G1) ∪L (G2).

Example:

S1 → aS1b

S1 → ǫ

S2 → cS2d

S2 → ǫ

S → S1

S → S2

Then L (G) = anbn:n≥0 ∪ cndn:n≥0anbn:n≥0 ∪ cndn:n≥0

2) Concatenation

G = (V1 ∪ V2 ∪ {S},∪_1 ∪_2, R, S) where R = R1 ∪ R2 ∪ {S → S1S2} and S is a new symbol.

Example:

S1 → aS1b

S1 → ǫ

S2 → cS2d

S2 → ǫ

S → S1S2

Then L(G) = anbncndn:m,n≥0anbncndn:m,n≥0

3) Kleene star

G = (V1 ∪ {S}, ∪_1, R, S) where R = R1 ∪ {S → ǫ, S → SS1} and S is a new symbol

Example:

S1 → aS1b

S1 → ǫ

S → ǫ

S → SS1

Then L(G) = anbn:n≥0anbn:n≥0

4) Non-closure properties

Context-free languages are not closed under intersection or complement.