GATE CS 1987 Q2k — Context-free Grammars and Push-down Automata

The given statement is FALSE (represented by 0).

Explanation:

Context-Free Languages (CFLs) are not closed under intersection. We can prove this using a classic counterexample:

1. Let $L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$. This language is context-free because we can use a pushdown automaton (PDA) to match the number of $a$'s with $b$'s, while ignoring the number of $c$'s.
2. Let $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$. This language is also context-free because we can match the number of $b$'s with $c$'s, while ignoring the number of $a$'s.

Now, let us find the intersection of $L_1$ and $L_2$:

The language $\{a^n b^n c^n \mid n \ge 0\}$ requires matching the counts of three different symbols ($a$, $b$, and $c$) simultaneously. A single stack in a PDA cannot perform this tracking, and it can be formally proven to be non-context-free using the Pumping Lemma for CFLs.

Since the intersection of two CFLs ($L_1$ and $L_2$) results in a non-CFL, the family of context-free languages is not closed under intersection.