GATE CS 2024 Set 1 | Question 23

MSQ · 1 mark

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. Option A: \(L_{1} = L_{2}\) if and only if \(L_{1} \cap \overline{L_{2}} = \phi\)
  2. Option B: \(L_{1} \cup L_{3}\) is not regular
  3. Option C: \(\overline{L_{3}}\) is not regular (correct)
  4. Option D: \(\overline{L_{1}} \cup \overline{L_{2}}\) is regular (correct)

Answer

(C), (D)

Explanation

Regular languages are closed under complement, union and intersection.

  • A: false. \(L_{1} \cap \overline{L_{2}} = \phi\) says only that no string of \(L_{1}\) lies outside \(L_{2}\), that is, \(L_{1} \subseteq L_{2}\). With \(L_{1} = \phi\) and \(L_{2} = \Sigma^{*}\) the condition holds but \(L_{1} \ne L_{2}\).
  • B: false. If \(L_{1} = \Sigma^{*}\), then \(L_{1} \cup L_{3} = \Sigma^{*}\), which is regular.
  • C: true. If \(\overline{L_{3}}\) were regular, its complement \(L_{3}\) would be regular too, which it is not.
  • D: true. \(\overline{L_{1}}\) and \(\overline{L_{2}}\) are regular, and so is their union.

Answer: C, D