GATE 2020 CS Q.8: solution and answer

GATE 2020 · CSQ.8 · 1 mark · MCQ

Consider the following statements.
I. If $L_{1} \cup L_{2}$ is regular, then both $L_{1}$ and $L_{2}$ must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE?

(A)
I only
(B)
II only
(C)
Both I and II
(D)
Neither I nor II

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Neither I nor II is true, so the answer is (D).

Official answer: DSource: Official answer key, GATE 2020 CS (IIT Delhi)

Statement I: take $L_{1} = Σ^{*}$ , which is regular, and $L_{2} = {a^{n} b^{n} ∣ n \geq 0}$ over $Σ = {a, b}$ , which is not regular (pumping lemma).
Then $L_{1} \cup L_{2} = Σ^{*}$ is regular, but $L_{2}$ is not regular. So Statement I is FALSE.
Statement II: closure of regular languages under union is guaranteed only for finitely many languages. It follows by induction from the two-language case, and induction does not extend to infinite unions.
Counterexample for an infinite union: each singleton ${a^{n} b^{n}}$ is finite, hence regular.
The union over all $n \geq 0$ is $⋃_{n \geq 0} {a^{n} b^{n}} = {a^{n} b^{n} ∣ n \geq 0}$ , which is not regular. So Statement II is FALSE.
Both statements are false, so the answer is (D) Neither I nor II.

KEY IDEA

Regular languages are closed under finite union only. Any language is a union of its singleton strings, and every singleton is regular, so closure under infinite union would make every language regular. Also, a union can be regular while a part of it is not, because $Σ^{*}$ absorbs anything.

WATCH OUT FOR

Assuming that closure under union extends to infinite unions, or that a regular union forces both parts to be regular.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 5 Regular languages questions, with notes

GATE 2020 CS Q.8: solution and answer

Answer and solution

More Regular languages questions