GATE CS 2017 Set 1 Q38 — Context-free Grammars and Push-down Automata

To determine which of the given languages are context-free, let us analyze $L_1$ and $L_2$ individually:

• $L_1 = \{a^n b^n c^m \mid m, n \ge 0\}$ is a Context-Free Language (CFL). A Pushdown Automaton (PDA) can push $a$'s onto the stack, pop them when reading $b$'s to ensure their counts match, and then read any number of $c$'s without modifying the stack.
• $L_2 = \{a^m b^n c^n \mid m, n \ge 0\}$ is also a CFL. A PDA can skip the initial $a$'s, push $b$'s onto the stack, and pop them when reading $c$'s to ensure their counts match.

Now, let us evaluate the given statements:

Statement I: $L_1 \cup L_2$

Context-free languages are closed under union. Since both $L_1$ and $L_2$ are CFLs, their union $L_1 \cup L_2$ is guaranteed to be a CFL.

Intuition: A non-deterministic PDA can make an initial $\epsilon$-transition to either the PDA for $L_1$ or the PDA for $L_2$.

Statement II: $L_1 \cap L_2$

Let us find the intersection of the two languages:

The language $\{a^n b^n c^n \mid n \ge 0\}$ is a well-known non-context-free language (which can be formally proven using the Pumping Lemma for CFLs). A single stack cannot simultaneously keep track of two independent comparisons (matching $a$'s with $b$'s, and then matching $b$'s with $c$'s).

Therefore, only I is a context-free language.