Closure Property of Context-Free Languages

 

Theorem 8.3 — Closure Properties of CFLs

The family of context-free languages is closed under union, concatenation, and star-closure.

That is,
If $L_{\mathrm{1and }}$$L_2$ are context-free languages, then

1. $L_1 \cup L_2$ is context-free.

2. $L_1{L}_2=\{xy\mathrm{\mid }x\in L_1,y\in L_2\}\; is\; context-free.$

3. $L_1^* = \{ x_1x_2...x_n \ | \ x_i \in L_1, n \ge 0 \}$ is context-free.

---

Proof

Let

$$G_1 = (V_1, T_1, S_1, P_1) \quad \text{and} \quad G_2 = (V_2, T_2, S_2, P_2)$$

be two context-free grammars generating $L_1$and $L_2$respectively.

Without loss of generality, assume that

$$V_1 \cap V_2 = \emptyset$$

—that is, the two grammars use disjoint sets of variables.

---

1. Closure under Union

Construct a new grammar

$$G_3 = (V_3, T_3, S_3, P_3)$$

where

• $V_3 = V_1 \cup V_2 \cup \{ S_3 \}$
  

• $T_3 = T_1 \cup T_2$

• $P_3 = P_1 \cup P_2 \cup \{ S_3 \rightarrow S_1 \ | \ S_2 \}$
  

That is, $S_3$ is a new start variable not in $V_1 \cup V_2$

So, $G_3$ contains all the productions of both grammars plus one extra production:

$$S_3 \rightarrow S_1 \ | \ S_2$$

Now, any derivation in $G_3$ begins with either $S_3 \Rightarrow S_1$ or $S_3 \Rightarrow S_2$.

• If $S_3 \Rightarrow S_1 \Rightarrow^* w$, then $w \in L_1$

• If $S_3 \Rightarrow S_2 \Rightarrow^* w$, then $w \in L_2$

Hence,

$$L(G_3) = L_1 \cup L_2$$

Since $G_3$ is a CFG, the union of two CFLs is a CFL.

---

2. Closure under Concatenation

Construct

$$G_4 = (V_4, T_4, S_4, P_4)$$

where

• $V_4 = V_1 \cup V_2 \cup \{ S_4 \}$
  

• $T_4 = T_1 \cup T_2$

• $P_4=P_1\cup P_2\cup \{S_4\to S_1{S}_2\}$

Thus, $G_4$ generates strings where something from $L_1$ is followed by something from $L_2$:

$$S_4 \Rightarrow S_1S_2 \Rightarrow^* w_1S_2 \Rightarrow^* w_1w_2$$

with $w_1 \in L_1$ and $w_2\in L_2$

Hence,

$$L(G_4) = L_1L_2$$

So, CFLs are closed under concatenation.

---

3. Closure under Kleene Star

Let

$$G_5 = (V_5, T_5, S_5, P_5)$$

where

• $V_5 = V_1 \cup \{ S_5 \}$
  

• $T_5 = T_1$

• $P_5 = P_1 \cup \{ S_5 \rightarrow S_1S_5 \ | \ \epsilon \}$
  

Now the grammar can either:

• Produce a string from $L_1$ and then repeat the process ($S_5 \rightarrow S_1S_5$), or

• Stop ($S_5 \rightarrow \epsilon$).

Thus, it generates any finite concatenation of strings from $L_1$:

$$L(G_5) = L_1^*$$

Therefore, CFLs are closed under the Kleene star operation.

---

✅ Conclusion

We have constructed context-free grammars for each of the three operations. Therefore:

$$\boxed{\text{The family of context-free languages is closed under union, concatenation, and star-closure.}}$$

---

🧩 Additional Note

CFLs are not closed under certain operations such as:

• Intersection

• Complement

• Difference

This is an important distinction—while regular languages are closed under all Boolean operations, context-free languages are not.