GATE CS 1996 Q2.8 — Context-free Grammars and Push-down Automata

Context-free languages (CFLs) have specific closure properties:

• Union ($L_1 \cup L_2$): Closed. If $L_1$ and $L_2$ are CFLs, their union is also a CFL.
• Concatenation ($L_1 \cdot L_2$): Closed. If $L_1$ and $L_2$ are CFLs, their concatenation is also a CFL.
• Intersection with a regular language ($L_1 \cap R$): Closed. The intersection of a CFL and a regular language is always a CFL.
• Intersection ($L_1 \cap L_2$): Not closed. The intersection of two CFLs is not necessarily a CFL.

For example, the languages $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$ are both context-free, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is a well-known non-context-free language.