GATE 2017 CS (CS1) – Question 48
Consider the following languages over the alphabet $\Sigma = \{a, b, c\}$. Let $L_1 = \{a^n b^n c^m \mid m, n \geq 0\}$ and $L_2 = \{a^m b^n c^n \mid m, n \geq 0\}$.
Which of the following are context-free languages?
I. $L_1 \cup L_2$
II. $L_1 \cap L_2$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) I only
Explanation
Each of $L_1$ and $L_2$ is context-free, and context-free languages are closed under union, so $L_1 \cup L_2$ is context-free. Their intersection is $\{a^n b^n c^n \mid n \geq 0\}$, which is not context-free. So only I holds.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2014 CS (CS1) Q25
- GATE 2014 CS (CS2) Q25
- GATE 2014 CS (CS2) Q46
- GATE 2016 CS (CS2) Q27
- GATE 2016 CS (CS2) Q28
- GATE 2016 CS (CS2) Q53
All Regular and Context-Free Languages, Pumping Lemma questions →