GATE CS 1989 Q3-ii — Regular and Context-free Languages

To determine which operations both Context-Free Languages (CFLs) and Regular Languages (RLs) are closed under, let us review their closure properties:

• Regular Languages are closed under all major operations, including Union, Intersection, Concatenation, and Complementation.
• Context-Free Languages are closed under:
  • Union: If $L_1$ and $L_2$ are CFLs, then $L_1 \cup L_2$ is also a CFL.
  • Concatenation: If $L_1$ and $L_2$ are CFLs, then $L_1 L_2$ is also a CFL.
  • Kleene Star: If $L$ is a CFL, then $L^*$ is also a CFL.

However, CFLs are not closed under:

• Intersection: For example, $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 CFLs, but their intersection $L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}$ is not a CFL.
• Complementation: Since $L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}$, closure under complementation and union would imply closure under intersection, which is a contradiction.

Thus, the operations under which both regular and context-free languages are closed are Union and Concatenation.