GATE 2021 CS (CS1) – Question 11
Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice
Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
- $L_1 \cap L_2$
- $L_1 \cdot L_2$
- $L_1 - L_2$
- $L_1 \cup L_2$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $L_1 - L_2$
Explanation
$L_1 - L_2 = L_1 \cap \overline{L_2}$, and CFLs are not closed under complement. The other three are always CFLs.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2020 CS Q18 – Consider the following statements. I. If L 1 L 2 is regular, then both L 1 and L 2 must be…
- GATE 2020 CS Q20 – Consider the language L=\an n 0\\anbn n 0\ and the following statements. I. L is…
- GATE 2020 CS Q42 – Consider the following languages. L 1=\wxyx w,x,y(0+1)+\ L 2=\xy x,y(a+b)*, x = y , x y\…
- GATE 2019 CS Q17 – If L is a regular language over = a,b , which one of the following languages is NOT…
- GATE 2019 CS Q25 – For =\a,b\, let us consider the regular language L=\x x=a2+3k or x=b10+12k,\ k0\. Which…
- GATE 2017 CS (CS1) Q48 – Consider the following languages over the alphabet = \a, b, c\. Let L 1 = \an bn cm m, n…
All Regular and Context-Free Languages, Pumping Lemma questions →