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) = ${a^n b^n: n ≥ 0}$. Also, L (G2) = ${c^n d^n: 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) = ${a^n b^n: n ≥ 0} \ \ ∪ \ \ {c^n d^n: 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) = ${a^n b^n c^n d^n: 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) = ${a^n b^n: n ≥ 0}$

4) Non-closure properties

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