The GATE Grind

GATE 2024 CS (CS1) – Question 23

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple select

Let $L_1,L_2$ be two regular languages and $L_3$ a language which is not regular. Which of the following statements is/are always TRUE?

  1. $L_1=L_2$ if and only if $L_1\cap\overline{L_2}=\phi$
  2. $L_1\cup L_3$ is not regular
  3. $\overline{L_3}$ is not regular
  4. $\overline{L_1}\cup\overline{L_2}$ is regular

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $\overline{L_3}$ is not regular; (D) $\overline{L_1}\cup\overline{L_2}$ is regular

Explanation

A fails: $L_1\cap\overline{L_2}=\phi$ only gives $L_1\subseteq L_2$. B fails (e.g., $L_3\cup\Sigma^*$ can be regular). C holds since regular languages are closed under complement. D holds by closure under complement and union.