GateAI
Regular and Context-Free Languages

GATE CSE 2020 · Q8

MCQ1 markEasy

Time

Consider the following statements. I. If L1∪L2L_1 \cup L_2 is regular, then both L1L_1 and L2L_2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: D) Neither I nor II

Regular and Context-Free Languages
  • Statement I is FALSE: The union of two non-regular languages can be regular. For example, let L1={anbn∣n≥0}L_1 = \{a^n b^n \mid n \ge 0\} (non-regular) and L2=Σ∗∖L1L_2 = \Sigma^* \setminus L_1 (non-regular). Then L1∪L2=Σ∗L_1 \cup L_2 = \Sigma^*, which is regular, but neither L1L_1 nor L2L_2 is regular.

  • Statement II is FALSE: Regular languages are closed under *finite* union, but not *infinite* union. Every non-regular language LL is the infinite union of singleton languages containing its strings: L=⋃w∈L{w}L = \bigcup_{w \in L} \{w\} Since each singleton set {w}\{w\} is regular, closure under infinite union would imply that every language is regular, which is a contradiction.

Therefore, neither I nor II is true, making (D) the correct answer.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Regular and Context-Free Languages previous year question is Q8 of the GATE CSE 2020 paper. Find more GATE CSE PYQs on Regular and Context-Free Languages in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular and Context-Free Languages PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Regular and Context-Free Languages in GATE CSE

Regular and Context-Free Languages has 21 GATE CSE PYQs across 13 papers from 2011 to 2026. 5 of them are 1-mark MCQs like this one, and GATE CSE 2020 has 2.

How GATE tests Regular and Context-Free Languages

More from GATE CSE 2020

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2020 · Q8 · MCQ

Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.