GATE CS 2017 Set 1 Q.38 (CS Q.38): Context-Free Grammars, Pushdown Automata and CFLs

Consider the following languages over the alphabet $\Sigma = \{a, b, c\}$ .

Let $L_1 = \{a^n b^n c^m \mid m, n \ge 0\}$ and $L_2 = \{a^m b^n c^n \mid m, n \ge 0\}$ .

Which of the following are context-free languages?

I. $L_1 \cup L_2$
II. $L_1 \cap L_2$

I only

II only

I and II

Neither I nor II

Official answer and solution

Official answer: A
From: Official GATE 2017 answer key

Solution

Apply context-free language closure properties under union and intersection.

We are given two languages over $\Sigma = \{a, b, c\}$ :

L_1 = \{a^n b^n c^m \mid m, n \ge 0\}

L_2 = \{a^m b^n c^n \mid m, n \ge 0\}

Both $L_1$ and $L_2$ are deterministic context-free languages (DCFLs):

For $L_1$ , a pushdown automaton pushes $a$ 's, pops on matching $b$ 's, and accepts while reading any number of $c$ 's.
For $L_2$ , a PDA skips $a$ 's, pushes $b$ 's, and pops on matching $c$ 's.

Statement I: $L_1 \cup L_2$ . Context-free languages are closed under union. If $S_1$ is the start symbol for $L_1$ and $S_2$ for $L_2$ , a new start symbol with rule $S \to S_1 \mid S_2$ generates $L_1 \cup L_2$ . Hence, $L_1 \cup L_2$ is a context-free language.

Statement II: $L_1 \cap L_2$ . The intersection requires both conditions to hold simultaneously:

L_1 \cap L_2 = \{a^n b^n c^n \mid n \ge 0\}

It is a classic result that $\{a^n b^n c^n \mid n \ge 0\}$ is not context-free (provable via the Pumping Lemma for CFLs). Hence, $L_1 \cap L_2$ is not a context-free language.

Thus, only I is a context-free language.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2017 Computer Science and Information Technology (CS) Session 1
Question: 38 of 65, printed as CS Q.38
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source